Boolesche Variable true iff Gleichung ist in ILP erfüllt

8

Unter der Annahme , y ist eine Boolesche Variable in einem Programm ILP (dh , st ) und , begrenzt ist ganzzahlige Variablen zwischen und . Ich möchte die folgende Einschränkung auf hoher Ebene codieren:0 < = y < = 1 x 1 x 2 0 M.yZ0<=y<=1x1x20M

y=1x1x2

Bisher habe ich folgendes:

x1x2+(M+1)y

Dies erzwingt, dass immer dann muss , wenn wahr ist, sonst gilt die Gleichung nicht. Wenn jedoch ist, schränkt nichts und könnte daher entweder oder . y 1 x 1x 2 y 0 1x1>x2y1x1x2y01

Welche andere Gleichung könnte ich hinzufügen, um die Einschränkung zu codieren?

Setzer22
quelle

Antworten:

5

Sie können dies tun, indem Sie die beiden Ungleichungen einführen

x1x2+M(1y)

und

x1>x2My.

Ersteres codiert die Anforderung (Sie können sehen, dass wenn , der Term verschwindet; wenn , dann wird etwas Großes und die Ungleichung wird automatisch erfüllt). Letzteres codiert die Anforderung (aus ähnlichen Gründen). y = 1 M ( 1 - y ) y = 0 M ( 1 - y ) y = 0y=1x1x2y=1M(1y)y=0M(1y)y=0x1>x2

Hoffentlich gibt Ihnen dies eine Vorstellung davon, wie Sie mit anderen Arten von Implikationen umgehen können, falls sie auftreten sollten. Grundsätzlich multiplizieren Sie mit etwas Großem und addieren / subtrahieren Sie es irgendwo.

DW
quelle
5

Sie können eine Konstante hinzufügen und dann diese Einschränkung hinzufügen:0<A<M

Ay(A+M)x1x2M(1y).

Wenn ist, bleiben Sie mity=1

Mx1x20,
was besagt, dass .x1x2

Und wenn ist, bleiben Sie mity=0

Ax1x2M,
das besagt, dass (da ).x1>x20<A<M
Ribz
quelle
3

Untersuchen Sie Indikator- und SOS-Einschränkungen. Während Sie die Zielbeziehungen linear definieren können, wie in anderen Antworten erläutert, können spezielle Einschränkungen vom IP-Solver effizienter behandelt werden.

Wenn Sie die Einschränkungen direkt implementieren möchten, wie in der anderen Antwort beschrieben, versuchen Sie, das kleinstmögliche M zu verwenden, und ziehen Sie in Betracht, die Integritätstoleranz zu verringern, wenn Ihr Ergebnis nicht korrekt ist. Vermeiden Sie außerdem strenge Ungleichungen, da diese im Kontext der Gleitkomma-Arithmetik nicht eindeutig sind.

Verwenden von Indikatoreinschränkungen:

x1x2y=1

x2x1+1y=0

Die zweite Einschränkung entspricht für ganze Zahlen. Wenn Sie x 2x 1 möchten, lassen Sie einfach die 1 fallen.x2>x1x2x1

Septimus G.
quelle
Danke für die hilfreichen Vorschläge! Können Sie erläutern, wie hilfreich / nützlich SOS-Einschränkungen in dieser speziellen Situation sind?
DW
Ich habe ein Beispiel mit Indikatorbeschränkungen hinzugefügt. Für SOS ist es komplizierter und Sie müssen zusätzliche Variablen einführen, sodass Sie möglicherweise nicht viel gewinnen, wenn Sie sie verwenden. Ich denke, der einzige Aspekt, bei dem man vorsichtig sein muss, sind die numerischen Probleme, die bei Verwendung der von anderen vorgeschlagenen Formulierungen auftreten können, und wie man sie lindert. Wenn Sie Zugriff auf einen Solver mit Indikatorbeschränkungen haben, versuchen Sie es auf diese Weise, da der Solver direkt darauf verzweigen oder den Big-M-Wert dynamisch ändern kann.
Septimus G