k-modカットを最小限に違反する方法(直感的な説明)?

背景として、私は理論的なコンピュータ科学の専門家ではない。しかし、私は研究レベルの最適化のトピックで試験を受ける必要があり、私はそれを自分で、講義や教師なしでそれを学ぶ必要があります。

整数プログラミングで学ぶ必要があるサブトピックの1つは、最大限mod-kカットに違反しています。私は一般的に切断面の方法を理解することができ、Chvatal-Gomoryが仕事をどのように削減するのかを理解することができました。私が使っている本では、制約不等式のシステムに何らかのベクトル$
λ$を掛け、すべての不等式を合計することによってk-modカットが作成されると書いています。私はこれを描写することが難しく、なぜこれが興味深い切り口につながるのか理解しています。

2つの変数と3つの不等式を持つ簡単なシステムから出発して数値的な例を作ってみましたが、何も思い付きませんでした(明らかに一般的なケースではNP困難です。非常に小さな例のために何度か試してみてください)。

これらの削減の背後にある直感について私に説明してください。彼らはどのように見えるのですか、それらを「最大限に違反させる」ことは、他の削減よりもどのように改善されていますか?


私が学ばなければならない主なテキストは、 http://www.springer.com/de/です。
book/9783642167287
と書いてありましたが、トピックについても、 http://www.lancaster.ac.uk/staff/letchfoa/articles/mod_k.pdf
を参照してください。彼らは研究レベルの情報源であり、定義を読む際に直感的な理解を得るための十分な背景がありません。

ベストアンサー

整数の線形プログラムがあり、次の制約が含まれているとします。

x1 + x2 + x3 >= 1, x1 + x2 + x4 >= 1, x1 + x3 + x4 >=
1, x2 + x3 + x4 >= 1.

x1、…、x4を1/3に設定すると、すべての制約を満たしますが、整数値はありません。

それぞれの制約に1/3を乗算し、それらを合計します。あなたは:

x1 + x2 + x3 + x4 >= 4/3.

変数は整数制約があるので、右辺を切り上げて次のように得られます。

x1 + x2 + x3 + x4 >= 2.

これは、上述の分数解を「切り捨てる」ので、「切断面」と呼ばれます。

制約条件に1/3を掛けたので、与えられたカットプレーンは「モディ3」カットです。さらに、部分解は、切断平面に2/3違反するので、可能である。したがって、モッズ3カットは「最大限に違反」されています。

より一般的には、mod-kカットを得るには、各拘束に1/kの倍数を掛けて、合計と丸めを行います。そのようなカットは、(k-1)/
kによって違反された場合、所与の部分解によって「最大限に違反」される。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です