Python の PuLP モジュールを使用して混合整数プログラミングでモデル化しようとしている次の制約があります。
与えられた線形計画法変数: x1,x2,y1,y2x1、x2、y1、y2 は最終的に整数値に解決されます
if (x1<=y2 and y1<=x2) then a=1 else b=0
Logical ANDで を処理する方法がわかりませんIF condition。が存在しない場合はAND、Big-M 表記を使用する必要があることがわかります。
質問する
2660 次
2 に答える
3
まず第一に、これは線形計画法ではなく混合整数計画AND法です。制約は線形ではなく、含意でもないからです。また、 と の両方がバイナリ変数であるaと仮定しました。b次に、問題を次のように再定式化できます。
x1 > y2 + m*z1
y1 > x2 + m*z2
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
ここで、mは (負の) 下限、つまりm < x1-y2とである必要がありm < y1-x2ます。z1とは両方ともz2バイナリ変数です。不等式を回避する<には、最初の 2 つの制約にいくつかの小さなイプシロンを追加することをお勧めします。
x1 >= y2 + (m-eps)*z1 + eps
y1 >= x2 + (m-eps)*z2 + eps
于 2017-01-10T07:57:54.510 に答える
2
IF-THEN-ELSE与えられた問題に関係なく機能する処方を見つけました。z1, z2回答の後半では、@ mattmilten の回答で説明されている変数を使用してAND condition、if statement
問題が次の仕様であると仮定します。
if α > 0 then β >= 0 else γ >= 0
それから、
α - z * U_α <= 0 # (1)
α - (1 - z)(L_α - 1) > 0 # (2)
β - (1 - z)L_β >= 0 # (3)
γ - z * L_γ >= 0 # (4)
どこ、
L_α, L_β, L_γ # are constant lower bounds on α, β, γ (or values smaller than the lowest value they can take)
U_α # is a constant lower bounds on α
z # is a LP variable that can take values {0,1}
z==1 の場合
その場合、式 (1) と (4) は冗長であり、then conditionまたは (3) が適用されます 。
z==0 の場合
その場合、式 (2) および (3) は冗長であり、else conditionまたは (4) が適用されます 。
この問題について
これを 2 回実行します。1 回目は α=α1 で、2 回目は α=α2 です。
どこ、
α1 = y2 - x1
z1 = decision variable for α1 with values {0,1}
α2 = y1 - x2
z2 = decision variable for α2 with values {0,1}
β # Currently unnecessary for my particular question.
γ # Currently unnecessary for my particular question.
したがって、制約は次のようになります。
α1 - z1 * U_α1 <= 0 # (1-1)
α1 - (1 - z1)(L_α1 - 1) > 0 # (1-2)
α2 - z2 * U_α2 <= 0 # (2-1)
α2 - (1 - z2)(L_α2 - 1) > 0 # (2-2)
z1=1 の場合、if 条件の最初の部分は true です。すなわち。x1<=y2
z2=1 の場合、if 条件の 2 番目の部分は true です。すなわち。x2<=y1
ここで、両方の条件を確保するために @mattmilten の定式化を使用します。
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
これにより、a=1 の場合、z1 と z2 の両方が >= 1 である必要があります。a=1 の場合、最後の条件に違反することなく、b は b=1 または b=0 のいずれかになります。
a=0 の場合、else 条件にあるため、b は 0 でなければなりません。
于 2017-01-11T22:20:38.260 に答える