私はリニアプログラム(または、必要ならばMIP)でオーバーラップしない制約(つまり、2つの長方形が重なり合わない)を書いています。制約プログラミングでそれを行う方法を知っています:
オブジェクトiとjの場合:
x [i] + dx [i]≦x [j] OR y [i] + dy [i]≦y [j] OR x [j] + dx [j] j] + dy [j]≦y [i] xとyはオブジェクトの座標を含む配列で、dxとdyはオブジェクトの次元です。
LP / MIPでこれを行う最善の方法のアイデア?ありがとう!
回答:
回答№1は1要約すると、制約プログラミング制約は
x[i]+dx[i]<=x[j] OR
y[i]+dy[i]<=y[j] OR
x[j]+dx[j]<=x[i] OR
y[j]+dy[j]<=y[i]
MIPモデルでは、これを次のようにモデル化できます。
x[i]+dx[i]<=x[j] + M*b[i,j,1]
y[i]+dy[i]<=y[j] + M*b[i,j,2]
x[j]+dx[j]<=x[i] + M*b[i,j,3]
y[j]+dy[j]<=y[i] + M*b[i,j,4]
sum(k, b[i,j,k])<=3
b[i,j,k] in {0,1}
ここで、Mは十分に大きな定数である( リンク)。
長方形iとjを比較した場合、jとiをもう比較する必要はありません。したがって、上の方程式では、 forall i<j
この対称性を利用する。