LinearProgrammierung: Nicht überlappende Einschränkung?

Question

Ich möchte eine nicht überlappende Einschränkung schreiben (das heißt, zwei Rechtecke überlappen sich nicht) in einem linearen Programm (oder einem MIP, falls erforderlich). Ich weiß, wie es in Constraint-Programmierung zu tun:

Für Objekt i und j:

x [i] + dx [i] < = x [j] OR y [i] + dy [i] < = y [j] ODER x [j] + dx [j] < = x [i] ODER y [j] + dy [j] < = y [i] wo x und y sind die Arrays mit den Koordinaten der Objekte und dx und dy sind die Dimensionen der Objekte.

Gibt es eine Vorstellung davon, wie dies am besten in LP/MIP funktioniert? Vielen Dank!

Answer 1

Fassen wir zusammen: Ihre Constraint-Programmierung Einschränkungen sind

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] 

In einem MIP-Modell Sie dies als modellieren:

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} 

wo M eine groß genug, um konstant ist (siehe link).

Wenn Sie Rechteck I und J verglichen haben, müssen Sie J und I nicht mehr vergleichen. In den obigen Gleichungen können wir forall i<j verwenden, um diese Symmetrie auszunutzen.