Welche Gewichte in speziellen geordneten Sets zu verwenden?

Question

Ich arbeite gerade an einem MIP-Problem, bei dem ich die speziell bestellten Sets vom Typ 2 (SOS2) nutzen kann.

Mein Problem ist, dass ich solche Sätze nicht vollständig verstanden habe. Der Grund dafür liegt in den Gewichtungen, die ich den Variablen in meinem SOS2 zuweisen muss.

Ich bin mir nicht sicher, was genau ich sollte ich zuweisen. Es gibt eine ziemlich klare Reihenfolge in meinem Set, aber ich bin mir nicht sicher, was die Gewichtungen sein sollten und nur 1,2,3 ... n zuzuteilen ist nicht korrekt, denke ich?

Also meine Frage ist, kann mir jemand erklären, was die Gewichte der Variablen in den speziellen geordneten Mengen sind und welche Werte sie zugewiesen werden sollten?

Answer 1

Zuerst definieren sie eine Reihenfolge. Speziell für SOS2-Sets gibt es das Konzept eines Nachbarn: In einem SOS2-Set können nur zwei benachbarte Variablen nicht-negativ sein. Einige Löser verwenden auch die Gewichte in ihrer Verzweigungsentscheidung. Dies kann nützlich sein, wenn Sie x Werte wie (1,2,3,10000) haben. Konsultieren Sie daher Ihre Solver-Dokumentation. Im Allgemeinen sollten SOS Gewichte einzigartig sein. Die Verwendung von (1,2,3,...) ist oft ein guter Standard, ansonsten verwenden Sie etwas wie die x-Werte (vorausgesetzt, Sie haben kein Segment parallel zur y-Achse).

Beachten Sie, dass in vielen Fällen eine Formulierung mit binären Variablen eine SOS-Formulierung übertrifft (dies ist insbesondere der Fall bei High-End-Solvern, die Formulierungen mit binären Variablen mit intelligenten Kürzungen versehen können). Einige Solver versuchen sogar automatisch, einige SOS-Sätze mithilfe binärer Variablen in ein Formular umzuformulieren.