リニアプログラミングにおけるIF/THENステートメントのモデリング

Question

ブール変数のセットX = {x0、x1、... xn}が与えられ、Xの各変数​​x \は1つのグループG = {g0、g1 ,. ...、GM}、グラム\サブセットX.

問題の目的は、どのように私はすべての必要とLPにおける制約をモデル化することができます。1.

に設定されているXの変数の数を最大化することですGの同じグループに属している変数は、0または1に設定されていますか？より正確には、G中のgからの2つのブール変数は、異なる値を持つことはできません。

P.S：上で定義した問題は、上で定義したもの以外の追加の制約を含む実際の問題を単純化したものです。

Answer 1

このような制約は凸ではないため、LPとして定式化することはできません。しかし、ILP（整数LP）のケース、すなわちNPタスクであるが、実際には妥当な数の変数に対して解決することができる。

0 <= x <= 1を制約することで、LPタスクをILPに簡単に拡張することもできます。最適値が0または1でない場合は、2つのLPを解決します.1つはxを0に固定し、もう1つは1に、 。すべての整数条件が満たされるまで繰り返します（再帰）。 （詳細については、Googleを使用してください）。

---

編集：あなたの特定の問題の割り当てを考えると、なぜあなただ​​けの1に等しいすべての変数を置くwould't？これは明らかに最大値であり、すべての可能なグループについて、2つの値が異なることはない（すべてが1であるため）。