Umgebung für ganzzahlige Programmierung
Lösen Sie ein kleines ganzzahliges lineares Programm mit exaktem Branch-and-Bound und sehen Sie alle Suchknoten. Die beste Lösung wird nur dann als nachweislich optimal gemeldet, wenn der gesamte Suchbaum untersucht wurde.
Programme sind auf 4.000 Zeichen und 40 Zeilen, 8 Variablen und 8 Nebenbedingungen mit mindestens zwei Variablen begrenzt; das Knotenlimit liegt zwischen 1 und 5.000, zudem endet die Suche nach 3.000.000 Schritten exakter Arithmetik. Alles wird auf Ihrem Gerät in einem Hintergrundprozess mit einem Zeitlimit von 15 Sekunden berechnet. Downloads: ein JSON-Bericht und eine CSV-Datei der Knoten. Erste Zeile: maximize oder minimize und die Zielfunktion. Danach folgt pro Zeile eine Nebenbedingung. Bis zu 4.000 Zeichen. Prüfe die Einstellungen vor dem Start.
Dein Ergebnis
Umgebung für ganzzahlige Programmierung
- Schreiben Sie die Zielfunktion in die erste Zeile, zum Beispiel maximize 5x + 4y.
- Geben Sie pro Zeile eine Nebenbedingung, Grenzen wie x, y >= 0 und optionale Zeilen wie integer x oder binary z an.
- Legen Sie das Knotenlimit fest und starten Sie die Suche.
- Lesen Sie den Status, die aktuelle ganzzahlige Lösung, die beste Schranke und den Abstand; laden Sie anschließend den JSON-Bericht oder die CSV-Datei der Knoten herunter.
Was du wissen solltest
Programme sind auf 4.000 Zeichen und 40 Zeilen, 8 Variablen und 8 Nebenbedingungen mit mindestens zwei Variablen begrenzt; das Knotenlimit liegt zwischen 1 und 5.000, zudem endet die Suche nach 3.000.000 Schritten exakter Arithmetik. Alles wird auf Ihrem Gerät in einem Hintergrundprozess mit einem Zeitlimit von 15 Sekunden berechnet. Downloads: ein JSON-Bericht und eine CSV-Datei der Knoten.
Branch and Bound
Jeder Knoten löst die lineare Relaxation mit dem Simplexverfahren exakt. Eine gebrochene ganzzahlige Variable wird in zwei Zweige aufgeteilt: x <= floor und x >= ceiling. Knoten werden verworfen, wenn ihre Relaxation unzulässig ist oder die bisher beste ganzzahlige Lösung nicht übertreffen kann. Methode: Wolsey, Integer Programming, 2. Auflage, Kapitel 7 (2020).
Was „bewiesen“ bedeutet
Wenn jeder Knoten gelöst oder mit einer exakten Schranke verworfen wurde, ist die aktuelle ganzzahlige Lösung als optimal bewiesen oder das Problem als unzulässig bewiesen. Beenden das Knotenlimit oder das Schrittekontingent die Suche vorher, ist die aktuelle Lösung lediglich der beste bisher gefundene Punkt; der Bericht zeigt die beste Schranke und den Abstand zwischen beiden.
Eingaberegeln
Variablen sind ganzzahlig, außer wenn Sie einige mit integer x, y als ganzzahlig deklarieren; die übrigen sind dann kontinuierlich. Nebenbedingungen mit nur einer Variablen werden zu Grenzen. Eine unbeschränkte Relaxation beendet die Suche, da das ganzzahlige Programm dann unbeschränkt oder unzulässig sein könnte.