Искам да напиша не припокриване ограничение (тоест, две правоъгълници не се припокриват) в линейна програма (или МИП, ако е необходимо) .Знам как да го направя в програмиране на ограничения:
За обекти i и j:
x [i] + dx [i] <= x [j] OR y [i] + dy [y] й] + ди [й] <= ш [Ь] където 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}
където М е достатъчно голяма константа (вж връзка).
Ако сте сравнявали правоъгълник i и j, вече не е нужно да сравнявате j и i. Така че в горните уравнения можем да използваме forall i<j да се възползва от тази симетрия.