Eu quero escrever uma restrição não sobreposta (ou seja, 2 retângulos não se sobrepõem) em um programa linear (ou um MIP, se necessário) .Eu sei como fazê-lo na programação de restrições:
Para o objeto i e j:
x [i] + dx [i] <= x [j] OU y [i] + di [i] <= y [j] OU x [j] + dx [j] <= x [i] OU y [ j] + dy [j] <= y [i] onde x e y são as matrizes contendo as coordenadas dos objetos e dx e dy são as dimensões dos objetos.
Alguma idéia da melhor maneira de fazer isso em LP / MIP? Obrigado!
Respostas:
1 para resposta № 1Para resumir: suas restrições de programação de restrições são
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]
Em um modelo MIP, você pode modelar isso como:
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}
onde M é uma constante grande o suficiente ligação).
Se você comparou o retângulo i e j, você não precisa mais comparar j e i. Então, nas equações acima, podemos usar forall i<j para explorar essa simetria.