Chcem napísať neprekrývajúce sa obmedzenie (to znamená, že dva obdĺžniky sa nepresahujú) v lineárnom programe (alebo MIP v prípade potreby) .Viem, ako to urobiť v programovaní obmedzenia:
Pre objekty i a j:
x [i] + dx [i] <= x [j] OR y [i] + dy [ j] + dy [j] <= y [i] kde x a y sú súradnice obsahujúce súradnice objektov a dx a dy sú rozmery objektov.
Akákoľvek predstavu o najlepšom spôsobe, ako to urobiť v LP / MIP? Vďaka!
odpovede:
1 pre odpoveď č. 1Ak chcete zhrnúť: obmedzenia vášho obmedzenia programovania sú
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]
V modeli MIP môžete modelovať takto:
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}
kde M je dostatočne veľká konštanta (pozri odkaz).
Ak ste porovnali obdĺžnik i a j, nemusíte porovnávať j a ja. Takže vo vyššie uvedených rovniciach môžeme použiť forall i<j využiť túto symetriu.