Voglio scrivere un vincolo non sovrapposto (cioè 2 rettangoli non sovrapposti) in un programma lineare (o un MIP se necessario) .Sono in grado di farlo in Programmazione con vincoli:
Per gli oggetti i e j:
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] dove x e y sono gli array che contengono le coordinate degli oggetti e dx e dy sono le dimensioni degli oggetti.
Qualche idea sul modo migliore di farlo in LP / MIP? Grazie!
risposte:
1 per risposta № 1Riassumendo: i vincoli di Programmazione Vincoli sono
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 un modello MIP è possibile modellarlo come:
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}
dove M è una costante abbastanza grande (vedi collegamento).
Se hai confrontato i rettangoli i e j non devi più confrontare j e i. Quindi nelle equazioni di cui sopra possiamo usare forall i<j sfruttare questa simmetria.