線形プログラムへのソリューションのランダム化された丸め

Question

整数線形プログラミング （ILP）は、組み合わせの最適化において非常に強力なツールです。 ILPのインスタンスとして問題を策定できる場合、ソルバーはグローバルな最適を見つけることが保証されています。ただし、統合ソリューションの実施には、最悪の場合に指数関数的なランタイムがあります。この障壁に対処するために、ILPに関連するいくつかの近似方法を使用できます。

• プライマルデュアルスキーマ
• ランダム化された丸め

プライマルデュアルスキーマは、貪欲なアルゴリズムを考え出し、リラックスしたデュアルLPを使用してその近似境界を証明する「パッケージ化された」方法を提供する多用途の方法です。結果として生じる組み合わせアルゴリズムは非常に高速であり、実際には非常にうまく機能する傾向があります。ただし、線形プログラミングとの関係は、分析に密接に関連しています。さらに、この分析のために、制約が違反されていないことを簡単に示すことができます。

ランダム化された丸めは異なるアプローチを取り、リラックスしたLP（インテリアポイントまたは楕円形の方法を使用）を解決し、ある確率分布に従って変数を丸めます。近似境界を証明できる場合、この方法は、プライマルデュアルスキーマのように非常に便利です。しかし、私にとっては1つの部分が明確ではありません。

ランダム化された丸めスキームは、制約に違反されていないことをどのように示していますか？

コインを素朴にひっくり返すと、0-1のソリューションになりますが、制約に違反する可能性があるようです。この問題を明らかにする助けがいただければ幸いです。ありがとうございました。

Answer 1

もちろん、丸めた場合、丸めが実現可能性を保持することを確認する必要があります。

たとえば、考えてみましょう リラックス Vertex-Cover LPの定式化。 $$ begin {array} {lll} text {min}＆ sum_ {v in v} c（v）x_v＆ text {st}＆x_u+x_v ge1、＆ quad（u、v ） in e ＆x_v ge 0.＆ quad v in v end {array} $$

この問題の解決策は半分統合であることが知られています。つまり、各変数は$ 0 $、$ 1 $、または$ 1/2 $のいずれかです。丸めスキームは次のように機能します、あなたのソリューションに$ x_v = 1/2 $ $が含まれているときはいつでもあなた 切り上げする $ x_v = 1 $を設定します。 ILPの制約は、$$ begin {array} {lll}＆x_u+x_v ge1、＆ quad（u、v） in e ＆x_v in {0,1 }でした。 ＆ quad v in v end {array} $$両方の制約は、丸め後に満たされます。そして、あなたは素晴らしい2つの承認を持っています。

Answer 2

はい、これは一見混乱しています。

私はそれがこのように見えます：

ステップ1）線形プログラムソリューションを生成します[ここではすべての線形プログラムの制約が満たされます - 整数ソリューションではないことを除いて]、

ステップ2）ランダム化（選択した確率分布に従って値を整数に変更します）、

ステップ3）ランダム化されたソリューションが正しいことを確認してください（変更を少なくすることで）。

たとえば、セットカバーで。ランダム化の後、必ずしもセットカバーではないセットのコレクションになってしまう可能性があります。この場合、覆われていないすべての要素をカバーするいくつかのセットを追加する必要があります（したがって、必要なソリューションを取得します）。

ランダム化された線形プログラムソリューションのこのような大きな変化を回避するために、丸め後に解決策が見つかる可能性が高いランダム化丸めスキームに従ってください（つまり、線形プログラムソリューションで多くの変更を行う必要はありません。欲しいです）。

参照については、これを参照してください。 1