線形計画法を使用して、以下の論理記述を解決したいと考えています。以下の例でn1, n2, n3, b1, b2, b3は、ブール変数です。
目的は最小化することc1です。
以下に制約を示します。
制約 1: (（n1==n2 xor n3） && c1==2 && b1 ) || ( (n1== n2 or n3) && c1==1 && b2 ) || (( n1 == n2 and n3) 1&& c1==3 && b3)
制約 2:n1 && n2== not n3
制約 3:only one of b1, b2, b3 is true
これらの論理制約を、Gurobi や lpsolve などの線形プログラミング ツールで必要な整数制約にエンコードすることは可能ですか? または、ブール制約を利用できるツールはありますか?
ありがとう。
混合整数計画法 (線形計画法ではない) で可能ですが、面倒です。簡単なものから始めましょう：
制約 2 :
n1 + n2 = 1 - n3
制約 3 :
b1 + b2 + b3 = 1 (if at most one of them is true then change = to <=)
制約 1 :
慣例:yブール変数zを表し、連続する非負変数を表すために使用します。&&また、 と の間にとANDの間に違いはないと仮定します。||OR
トリックは、それを断片に分解し、各断片を個別の変数として定義することです..
y1 := n1==n2 --> (（y1 xor n3） && c1==2 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
y1 >= 1 - (n1 + n2)
y1 >= (n1 + n2) - 1
y1 <= 2 - 2n1 + n2
y1 <= 2 - 2n2 + n1
y2 := y1 xor n3 --> (y2 && c1==2 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
y2 <= y1 + x3
y2 >= y1 - x3
y2 >= x3 - y1
y2 <= 2 - y1 - x3
y5 := c1==2 --> (y2 && y5 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
を事前epsilon > 0定義された許容値 ( の場合2 - epsilon <= c1 <= 2 + epsilon)c1=2とM大きな数 ( の上限の可能性があるc1) にする:
z3 >= c1 - 2 + epsilon*y3; z3 >= 0
z4 >= 2 - c1 + epsilon*y4; z4 >= 0
z3 <= My3
z4 <= My4
y3 + y4 + y5 = 1
y6 := y2 && y5 && b1 --> y6 || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
y6 <= y2
y6 <= y5
y6 <= b1
y6 >= y2 + y5 + b1 - 2
y7 := y1 or n3 --> y6 || ( y7 && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
y7 >= y1
y7 >= n3
y7 <= y1 + n3
y10 := c1 == 1 --> y6 || ( y7 && y10 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)
z8 >= c1 - 1 + epsilon*y8; z8 >= 0
z9 >= 1 - c1 + epsilon*y9; z9 >= 0
z8 <= My8
z9 <= My9
y8 + y9 + y10 = 1
y11 := y7 && y10 && b2 --> y6 || y11 || (( y1 and n3) 1&& c1==3 && b3)
y11 <= y7
y11 <= y10
y11 <= b2
y11 >= y7 + y10 + b2 - 2
1&&がタイプミスであり、実際には であると仮定すると&&、
y12 := ( y1 and n3) --> y6 || y11 || (y12 && c1==3 && b3)
y12 <= y1
y12 <= n3
y12 >= y1 + n3 - 1
y15 := c1==3 --> y6 || y11 || (y12 && y15 && b3)
z13 >= c1 - 3 + epsilon*y13; z13 >= 0
z14 >= 3 - c1 + epsilon*y14; z14 >= 0
z13 <= My13
z14 <= My14
y13 + y14 + y15 = 1
y16 := y12 && y15 && b3 --> y6 || y11 || y16
y16 <= y12
y16 <= y15
y16 <= b3
y16 >= y12 + y15 + b3 - 2
ついに、y6 || y11 || y16
y6 + y11 + y16 >= 1
これが役立つことを願っています。便宜上、完全な数学的モデルを以下に示します。
数学的モデル
min c1
s.t. n1 + n2 = 1 - n3
b1 + b2 + b3 = 1
y1 >= 1 - (n1 + n2)
y1 >= (n1 + n2) - 1
y1 <= 2 - 2n1 + n2
y1 <= 2 - 2n2 + n1
y2 <= y1 + x3
y2 >= y1 - x3
y2 >= x3 - y1
y2 <= 2 - y1 - x3
z3 >= c1 - 2 + epsilon*y3; z3 >= 0
z4 >= 2 - c1 + epsilon*y4; z4 >= 0
z3 <= My3
z4 <= My4
y3 + y4 + y5 = 1
y6 <= y2
y6 <= y5
y6 <= b1
y6 >= y2 + y5 + b1 - 2
y7 >= y1
y7 >= n3
y7 <= y1 + n3
z8 >= c1 - 1 + epsilon*y8; z8 >= 0
z9 >= 1 - c1 + epsilon*y9; z9 >= 0
z8 <= My8
z9 <= My9
y8 + y9 + y10 = 1
y11 <= y7
y11 <= y10
y11 <= b2
y11 >= y7 + y10 + b2 - 2
y12 <= y1
y12 <= n3
y12 >= y1 + n3 - 1
z13 >= c1 - 3 + epsilon*y13; z13 >= 0
z14 >= 3 - c1 + epsilon*y14; z14 >= 0
z13 <= My13
z14 <= My14
y13 + y14 + y15 = 1
y16 >= y12
y16 >= y15
y16 >= b3
y16 >= y12 + y15 + b3 - 2
y6 + y11 + y16 >= 1
y1, ..., y16, b1, b2, b3, n1, n2, n3 binary
z3, z4, z8, z9, z13, z14 >= 0
ちなみに、両方にアクセスできる場合はlpsolve、Gurobi間違いなく選択してGurobiください。これは市場のリーダーであり、lpsolveのパフォーマンスは、ある程度複雑なほとんどの問題とはかけ離れています。
アップデート
このモデルをソルバーに入れた後、解を得てc1 = 1、
n1 = 1
n2 = 1
n3 = 1
b1 = 0
b2 = 1
b3 = 0
どちらが理にかなっていますか:c1 == 1またはc2 == 2orc3 == 3節 3 が真であり、ケースc1=1は可能な限り最小限です。他の変数の値を差し込むと、3 つの制約がすべて満たされていることがわかります。