LinearProgramming：重複しない制約？

Question

リニアプログラム（または必要に応じてMIP）でオーバーラップしない制約（つまり、2つの長方形が重ならない）を書きたいとします。私は、制約プログラミングでそれを行う方法を知っている：

オブジェクトの場合、iとj：

X [i]が+ DX [i]を< = xの[J]またはy [i]が+ DY [i]の< < = x [i] < = y [i] ここで、xとyは座標の座標を含む配列です。オブジェクトとdxとdyはオブジェクトの次元です。

LP/MIPでこれを行う最善の方法はありますか？ありがとう！要約する

Answer 1

：

Mが十分な大きさの定数（ linkを参照）である

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} 

：あなたの制約プログラミングの制約は、あなたがこれをモデル化することができMIPモデルで

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] 

です。

長方形iとjを比較した場合、jとiをもう比較する必要はありません。したがって、上記の式では、forall i<jを使用してこの対称性を利用することができます。