Ganzzahlige Programme |
Wir kommen noch einmal auf unser Muffin Teig Problem zurück:
\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \text{subject to} \quad & 0.8 x_1 + 0.5 x_2 \leq 1500 \\ & 0.2 x_1 + 0.5 x_2 \leq 900 \\ & x_1 \geq 0 \\ & x_2 \geq 0 \end{aligned} \]
Angenommen ein Muffin besteht immer aus 175g Teig.
Unsere Lösung war $x_1 = 1000$ und $x_2 = 1400$.
Wir können also 5 Muffins von Typ A und 8 Muffins von Typ B herstellen. Vom A Teig bleiben 125g ungenutzt übrig.
Ist das die beste Lösung?
Nicht notwendigerweise!
Wir wollen die beste Lösung unter der Annahme, dass nur diskrete Anzahlen an Muffins möglich sind.
Wir formulieren das Problem so um, dass wir die Anzahl an Muffins je Typ zählen.
Integer Linear Program (ILP oder IP)
Wenn wir stetige und ganzzahlige Variablen haben, sprechen wir von
Mixed Integer Linear Programming (MILP oder MIP).
Wir erlauben nur noch ganzzahlige Punkte innerhalb der Nebenbedingungen:
Durch Abrunden erreichen wir diese Lösung:
Die Lösung bringt Einnahmen von 1225;
Woher wissen wir, ob es eine bessere Lösung gibt?
Wie finden wir allgemein die beste Lösung?
Idee: Divide & Conquer
Wenn wir das Problem als LP lösen bekommen wir
\[ x = \begin{bmatrix} 5.714 \\ 8 \end{bmatrix} \]In der endgültigen Lösung hat $x_1$ zwei Möglichkeiten: \[ x_1 \leq 5 \quad\text{oder}\quad x_1 \geq 6 \]
Wir können also nun die zwei LPs lösen:
| \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_1, x_2 \geq 0 \end{aligned} \] | \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \] |
Für jedes LP erhalten wir wieder eine Lösung
$x = \begin{bmatrix} 5 \\ 8.286 \end{bmatrix}, \text{obj} = 1250$ |
$x = \begin{bmatrix} 6 \\ 7.543 \end{bmatrix}, \text{obj} = 1290$ |
Ähnlich können wir weitermachen. Für den ersten Abzweig können wir wieder zwei Varianten formulieren:
| \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_2 \leq 8 \\ & x_1, x_2 \geq 0 \end{aligned} \] | \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_2 \geq 9 \\ & x_1, x_2 \geq 0 \end{aligned} \] |
Jeder neue Abzweig hat wieder eine Lösung:
$x = \begin{bmatrix} 5 \\ 8 \end{bmatrix}, \text{obj} = 1225$ |
$x = \begin{bmatrix} 3.214 \\ 9 \end{bmatrix}, \text{obj} = 1125$ |
In der Variante $x_1 \leq 5, x_2 \leq 8$ haben wir nun eine zulässige, ganzzahlige Lösung gefunden.
Das ist auch die Lösung, die wir vorhin durch Runden hatten.
In diesem Abzweig sind wir fertig. Kein anderer Punkt kann besser sein.
In dem anderen Abzweig war unsere Lösung wieder fraktional:
|
|
$x = \begin{bmatrix} 3.214 \\ 9 \end{bmatrix}, \text{obj} = 1125$ Müssen wir hier nun |
Die beste fraktionale Lösung in dem Abzweig hat Zielfunktionswert 1125.
Wir haben schon eine ganzzahlige Lösung mit Zielfunktionswert 1225 gefunden.
Wir können also den ganzen Zweig abschneiden.
In der noch offenen Variante $x_1 \geq 6$ hatte die fraktionale Lösung Zielfunktionswert 1290.
Hier sind wir also noch nicht fertig.
Wieder zerlegen wir das Problem in zwei Teile:
| \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1, x_2 \geq 0 \end{aligned} \] | \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \geq 8 \\ & x_1, x_2 \geq 0 \end{aligned} \] |
$x = \begin{bmatrix} 6.339 \\ 7 \end{bmatrix}, \text{obj} = 1278.125$ |
Unlösbar |
Den unlösbaren Abzweig können wir direkt abschneiden.
In dem anderen Abzweig unterteilen wir weiter.
| \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \leq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \] | \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_1, x_2 \geq 0 \end{aligned} \] |
$x = \begin{bmatrix} 6 \\ 7 \end{bmatrix}, \text{obj} = 1242.5$ |
$x = \begin{bmatrix} 7 \\ 5.943 \end{bmatrix}, \text{obj} = 1255$ |
Wir haben eine neue ganzzahlige Lösung gefunden. Deren Zielfunktionswert von 1242.5 ist sogar besser als der Alte von 1225.
Die alte Lösung können wir nun vergessen. Wir brauchen immer nur die (bisher) beste Lösung.
Was können wir an dieser Stelle über Qualität der (bisher besten) Lösung sagen?
- Die aktuell beste ganzzahlige Lösung hat ZFW 1242.5
- Die beste (noch offene) fraktionale Lösung hat ZFW 1255
$\Rightarrow$ Es kann keine ganzzahlige Lösung geben, die unseren aktuellen ZFW um mehr als 12.5 (1%) verbessert.
Den Abstand zwischen aktuell bester Lösung und der besten offenen fraktionalen Lösung nennen wir
Optimality Gap.
Sollten wir mit das Lösen jetzt aufgeben, haben wir zumindest diese Qualitätsgarantie.
Wenn wir nicht aufgeben, müssen wir hier noch weiter aufteilen:
$x = \begin{bmatrix} 7 \\ 5.943 \end{bmatrix}, \text{obj} = 1255$
| \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_2 \leq 5 \\ & x_1, x_2 \geq 0 \end{aligned} \] | \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_2 \geq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \] |
$x = \begin{bmatrix} 7.589 \\ 5 \end{bmatrix}, \text{obj} = 1234.375$ |
Unlösbar |
Im ersten Abzweig sind wir nun zu schlecht und im anderen gibt es keine Lösung.
Wir sind also fertig und wissen:
$x = \begin{bmatrix} 6 \\ 7 \end{bmatrix}$ ist die global beste Lösung mit ZFW 1242.5
- Die LP Lösung bereits ganzzahlig ist.
- Das Teilproblem infeasible ist.
- Die fraktionale Lösung schlechter als die beste bisher gefundene ganzzahlige Lösung ist.
Wir müssen einen Knoten nicht weiter aufteilen wenn:
Branch & Bound
Den besten ganzzahligen Zielfunktionswert, den wir kennen nennen wir primale Schranke.
Wir wissen, dass wir keine Lösung mit schlechterem ZFW akzeptieren müssen.
Den besten Zielfunktionswert über alle aktuellen (nicht geprunten) Blätter nennen wir duale Schranke.
Wir wissen, dass es keine Lösung geben kann, welche diesen ZFW übertrifft.
Wenn wir einen Knoten aufteilen, kann der Zielfunktionswert der Kinder niemals besser werden
(und verschlechtert sich tendenziell).
Jeder Kinderknoten hat mehr Constraints als der Eltnernknoten.
Die primale Schranke kann nie besser sein, als die duale Schranke.
Ganzzahligkeit ist eine zusätzliche Einschränkung die uns höchstens schlechter macht.
Bei einem Maximierungsproblem steigt mit der Zeit die primale Schranke und die duale Schranke sinkt.
Bei einem Minimierungsproblem ist es umgekehrt.
Die optimality gap
\[ \frac{|\text{duale Schranke} - \text{primale Schranke}|}{|\text{primale Schranke}|} \]gibt an, wie viel unsere bisher beste Lösung eventuell noch verbessert werden könnte.
Wir haben nun einen Algorithmus, der auf jeden Fall irgendwann die global optimale Lösung für unser ILP findet.
Wie viel Rechenaufwand braucht der?
Im schlimmsten Fall ist die Anzahl an Knoten exponentiell in der Anzahl an Variablen (und deren möglichen Werten).
Unsere Aussicht auf einen gut skalierenden Algorithmus ist schlecht.
Integer Programming ist NP-schwer.
Dafür können wir jedes NP-schwere als ILP abbilden.
Integer Programming ist NP-vollständig.
Vorteil: viele Probleme lassen sich sehr gut als ILP modellieren.
- Unser Algorithmus garantiert, dass er immer Fortschritte Richtung globalem Optimum macht.
- Wir haben immer eine Gütegarantie der aktuellen Lösung (falls wir abbrechen).
- Moderne ILP Solver sind für viele Probleme sehr schnell.
Weitere Vorteile von ILPs:
- Simplex in Kind Knoten "warm starten"
- Heuristiken zum finden guter ganzzahliger Lösungen
- Neue Nebenbedingungen ableiten, die garantiert erfüllt sein müssen und die duale Schranke verbessern.
Durch viele Tricks kann man Branch & Bound verbessern:
Beispiel für abgeleitete Nebenbedingungen:
\[ x_1 + x_2 \leq 1 \quad x_1 + x_3 \leq 1 \quad x_2 + x_3 \leq 1 \\ \]\[ \Rightarrow x_1 + x_2 + x_3 \leq 1 \] (Clique Cover)
Das ist ein recht aktives Forschungsfeld.
In den Jahren 2001 bis 2020 sind die Solver jedes Jahr im Durchschnitt 22% schneller geworden.
Faktor 50 über 20 Jahre.
Die Hardwareverbesserungen (Faktor 20) kommen da noch oben drauf (Faktor 1000 insgesamt).
Fortschritte sind ungleich verteilt: Manche Problemklassen funktionieren besser als andere.
- COIN-OR CBC (Open Source)
- CPLEX (kommerziell)
- GLPK (Open Source)
- Gurobi (kommerziell)
- SCIP (Open Source)
Leistungsfähige MILP Solver:
Bei den LP Modellen hatten wir Fälle, wo wir eigentlich auch Ganzzahligkeit hätten fordern müssen.
- Matching von Studierenden zu Übungsgruppen
- Kürzester Weg in einem Graphen
Beispiel: Studierenden Matching
\[ \begin{aligned} \max\quad & \sum_{i,j} p_{ij} x_{ij} \\ \text{s.t.}\quad &\sum_j x_{ij} = 1 \quad & \forall i \\ &\sum_i x_{ij} \leq 5 \quad & \forall j \\ &x_{ij} \geq 0 \quad & \forall i,j \end{aligned} \]Man kann hier beweisen, dass in diesen Fällen die Ecken von dem Polyeder immer ganzzahlig sind.
Wir bekommen also automatisch eine ganzzahlige Lösung.
Wir können zur Sicherheit immer Ganzzahligkeit fordern (wenn benötigt). Es kostet ja keine Performance wenn der erste Knoten schon ganzzahlig ist.
Nachteile von ILPs gegen LPs:
- Performance
- Keine Schattenpreise