Zerlegen und beweisen

Manche Planungsprobleme sind zu groß, um sie in einem Stück zu lösen. Die Benders-Dekomposition zerlegt sie in ein Hauptproblem und viele Teilprobleme, die sich über einfache Geraden verständigen. Sind die Teilprobleme ganzzahlig, versagen die klassischen Geraden – dann helfen Lagrange-Cuts.

Ein Cloud-Anbieter muss heute entscheiden, an welchen Standorten er Rechenzentren betreibt. Wie viel Rechenleistung seine Kunden im nächsten Jahr verlangen, weiß er erst später. Ein Energieversorger plant Kraftwerke, bevor er Wetter und Strompreise der kommenden Jahre kennt. Ein Logistiker eröffnet Lager, bevor die Bestellungen eingehen. In allen drei Fällen fällt eine Entscheidung vor dem Zufall, und danach wird auf den Zufall reagiert. Fachleute sprechen von zweistufiger stochastischer Optimierung.

Solche Probleme werden schnell riesig. Jede denkbare Zukunft – jedes Szenario – bringt ein eigenes Planungsproblem mit, und alle hängen an derselben ersten Entscheidung. Die Benders-Dekomposition, benannt nach dem niederländischen Mathematiker Jacques F. Benders, nutzt genau diese Struktur: Ein Masterproblem schlägt eine erste Entscheidung vor, die Teilprobleme bewerten sie, und aus jeder Bewertung entsteht eine Gerade, die dem Masterproblem eine Lehre mitgibt. Diese Geraden heißen Cuts.

Dieses Dossier erklärt das übliche Vorgehen von Grund auf: was die Wertfunktion ist, wann ein Cut gültig und wann er straff ist, warum zwei Schranken einen Beweis liefern, wie man Cuts aus der Dualität linearer Programme gewinnt – und warum man bei ganzzahligen oder nichtkonvexen Teilproblemen zu Lagrange-Cuts greift. Am Ende steht ein vollständig durchgerechnetes Beispiel und eine Lesehilfe für Fachartikel. Vorausgesetzt wird nur Schulmathematik: Geraden, Gleichungen und der Erwartungswert.

Drei Ideen tragen das ganze Verfahren

Der rote Faden

Die Kapitel bauen aufeinander auf. Jeder Schritt der folgenden Abfolge wird in einem eigenen Kapitel erklärt.

1. 1Schranken und Lückewie man Optimalität beweist
2. 2Zweistufiges Problemheute entscheiden, morgen reagieren
3. 3WertfunktionFolgekosten jeder Entscheidung
4. 4CutsGeraden unter der Wertfunktion
5. 5Benders-Verfahrenvorschlagen, bewerten, dazulernen
6. 6LP-Dualitätklassische Cuts, versagen bei Ganzzahligkeit
7. 7Lagrange-Cutsgültig für jede Steigung
8. 8Multiplikatorsucheder teure Teil
9. 9Kernpunktewelcher Cut am meisten hilft

Wie man dieses Dossier liest

Wer schnell zum Kern will, liest Kapitel 4 (Wertfunktion), Kapitel 5 (Benders-Verfahren), Kapitel 7 (Lagrange-Cuts) und das Beispiel in Kapitel 9. Wer gründlich vorgehen möchte, beginnt mit dem Handwerkszeug in Kapitel 2. Kapitel 12 ist ein Nachschlageteil: Es übersetzt die Symbole und typischen Wendungen aus Fachartikeln und nennt jeweils das Kapitel, in dem sie erklärt werden.

Formeln sind unvermeidlich, aber jede wird in Worten erklärt und am Beispiel mit Zahlen gefüllt. Wer eine Formel überspringt, verliert den Faden nicht.

Das Beispiel, das uns begleitet

Durch das ganze Dossier zieht sich ein kleines Planungsproblem: Ein Cloud-Anbieter kann an drei Standorten – Nord, Mitte und Süd – Server aufstellen. Danach zeigt sich, ob das kommende Jahr ruhig verläuft oder Spitzenlast bringt, und vier Kundenregionen müssen auf die Standorte verteilt werden. Was nicht ins eigene Netz passt, wird teuer bei einer fremden Cloud eingekauft. Das Problem ist so klein, dass man jede Zahl von Hand nachrechnen kann, und doch groß genug, um alle Effekte zu zeigen: Die klassischen Cuts bleiben darin stecken, die Lagrange-Cuts beweisen die beste Lösung in sechs Runden, und ein gut gewählter Cut schafft es in zwei.

Bevor es um Zerlegung geht, braucht es ein paar Grundbegriffe: was ein Optimierungsproblem ist, warum ganze Zahlen alles schwerer machen und wie man beweist, dass eine Lösung die beste ist.

2.1 Was ein Optimierungsproblem ist

Ein Optimierungsproblem besteht aus drei Teilen. Die Entscheidungsvariablen sind das, was man festlegen darf – etwa, welche Standorte geöffnet werden. Die Zielfunktion bewertet jede Entscheidung, meist als Kosten, die möglichst klein sein sollen. Die Nebenbedingungen grenzen ein, was erlaubt ist – etwa, dass ein Standort nicht mehr Last tragen kann, als seine Kapazität hergibt. Eine Entscheidung, die alle Nebenbedingungen erfüllt, heißt zulässig; die zulässige Entscheidung mit den geringsten Kosten heißt optimal.

Mathematisch schreibt man das kurz als „min f(x) unter der Bedingung x ∈ X“: Gesucht ist das kleinste f(x) unter allen x aus der zulässigen Menge X. Der kleinste erreichbare Wert heißt Optimalwert.

2.2 Lineare und ganzzahlige Programme

Sind Zielfunktion und Nebenbedingungen linear – also nur Summen von Variablen mal Zahlen –, spricht man von einem linearen Programm (LP). Lineare Programme sind gutmütig: Selbst mit Millionen Variablen löst ein Computer sie in Sekunden bis Minuten. Das Wort „Programm“ ist dabei alt und meint „Plan“, nicht Software.

Viele Entscheidungen sind aber nicht beliebig teilbar. Ein Standort ist offen oder geschlossen, ein Kunde wird von einem Rechenzentrum bedient oder nicht. Solche Ja-Nein-Entscheidungen werden mit binären Variablen dargestellt, die nur 0 oder 1 sein dürfen. Ein lineares Programm mit ganzzahligen Variablen heißt gemischt-ganzzahliges Programm (englisch mixed-integer program, MIP).

Der Grund für den Rechenaufwand ist schlichtes Abzählen. Mit drei Standorten gibt es 2 · 2 · 2 = 8 mögliche Kombinationen, mit zehn schon 1024, mit fünfzig mehr als eine Billiarde. Gute Verfahren müssen nicht alle durchprobieren, doch im ungünstigen Fall wächst der Aufwand exponentiell.

2.3 Relaxation: absichtlich zu großzügig sein

Eine Relaxation ist eine gelockerte Fassung eines Problems: Man streicht eine Nebenbedingung oder schwächt sie ab. Das bekannteste Beispiel ist die LP-Relaxation: Statt „0 oder 1“ erlaubt man jeden Wert zwischen 0 und 1. Ein Kunde darf dann zur Hälfte von Nord und zur Hälfte von Süd bedient werden.

Das Entscheidende: Wer mehr erlaubt, kann nur gleich gut oder besser abschneiden. Bei einem Kostenminimum ist der Optimalwert der Relaxation deshalb nie größer als der des Originals. Jede Relaxation liefert so eine untere Schranke – eine Zahl, unter die die wahren Kosten nicht fallen können.

2.4 Schranken, Lücke und Zertifikat

Zwei Zahlen rahmen jedes Minimierungsproblem ein:

Ist die Lücke null, ist die Lösung bewiesen optimal. Ist sie zwei Prozent, weiß man: Die gefundene Lösung ist höchstens zwei Prozent teurer als die beste. Das Paar aus beiden Schranken heißt deshalb ein Zertifikat – ein Nachweis, den jeder prüfen kann, ohne dem Rechenweg vertrauen zu müssen.

2.5 Wie ein Solver ganzzahlige Probleme löst

Programme, die Optimierungsprobleme lösen, heißen Solver; bekannte Namen sind Gurobi, CPLEX, Xpress, SCIP und HiGHS. Für ganzzahlige Probleme nutzen sie im Kern Branch-and-Bound: Sie lösen die LP-Relaxation, teilen das Problem an einer gebrochenen Variablen in zwei Fälle („Standort Nord zu“ und „Standort Nord offen“) und verwerfen ganze Zweige, sobald deren untere Schranke schlechter ist als die beste bekannte Lösung. Dazu kommen Schnittebenen, Heuristiken und viele Kniffe.

Für dieses Dossier ist eine Eigenschaft wichtig: Ein Solver führt laufend beide Schranken mit. Bricht man ihn nach einem Zeitlimit ab, liefert er die beste gefundene Lösung und eine gültige untere Schranke – auch wenn die Lücke noch nicht geschlossen ist. Ein einzelner Aufruf eines Solvers heißt in Fachartikeln oft einfach „ein Solve“.

2.6 Dualität und Schattenpreise

Zu jedem linearen Programm gehört ein zweites, das duale Programm. Seine Variablen sind Preise für die Nebenbedingungen. Ein solcher Schattenpreis sagt, um wie viel sich der Optimalwert ändert, wenn man die rechte Seite einer Nebenbedingung um eine Einheit verschiebt – etwa: Wie viel Kosten spart eine zusätzliche Einheit Kapazität?

Zwei Sätze machen die Dualität so nützlich. Die schwache Dualität: Jede zulässige Lösung des dualen Programms liefert eine untere Schranke für das ursprüngliche Problem. Die starke Dualität: Im Optimum sind beide Werte gleich. Bei linearen Programmen beschreibt das duale Programm das ursprüngliche also vollständig. Bei ganzzahligen Programmen gilt nur die schwache Fassung; zwischen beiden Werten bleibt im Allgemeinen eine Dualitätslücke. Genau an dieser Stelle setzen später die Lagrange-Cuts an.

2.7 Eine kleine Lesehilfe für Formeln

Zweistufige stochastische Programme beschreiben eine Grundsituation des Planens: Man muss sich festlegen, bevor man die Zukunft kennt, und darf später nur noch nachsteuern. Ihre Struktur ist der Schlüssel zur Zerlegung.

3.1 Heute entscheiden, morgen reagieren

In der ersten Stufe fällt eine Entscheidung x, die sich später nicht mehr ändern lässt: Standorte, Kraftwerke, Verträge. Dann tritt der Zufall ein – die Nachfrage, das Wetter, der Preis. In der zweiten Stufe wird mit Entscheidungen y darauf reagiert: Kunden werden zugeordnet, Kraftwerke hochgefahren, Fehlmengen zugekauft. Diese Reaktion heißt im Fachjargon auch Rekurs (englisch recourse).

Die erste Entscheidung soll so gewählt werden, dass ihre eigenen Kosten und die erwarteten Kosten der Reaktion zusammen möglichst klein sind. Sie muss also gegen alle möglichen Zukünfte zugleich bestehen – das macht sie anders als eine Planung für den Durchschnittsfall.

3.2 Szenarien und Wahrscheinlichkeiten

Der Zufall wird durch endlich viele Szenarien s = 1, …, S dargestellt, jedes mit einer Wahrscheinlichkeit p_s. Die Wahrscheinlichkeiten addieren sich zu eins. In der Praxis stammen die Szenarien aus historischen Daten oder werden aus einer Verteilung gezogen; mehr Szenarien bilden die Unsicherheit genauer ab, machen das Problem aber größer.

Die erwarteten Folgekosten sind dann ein gewichteter Durchschnitt: Folgekosten in Szenario 1 mal p₁ plus Folgekosten in Szenario 2 mal p₂ und so weiter – der Erwartungswert.

3.3 Die Formel und was sie sagt

In Fachartikeln steht das zweistufige Problem meist in dieser Form:

Gelesen: Wähle die erste Entscheidung so, dass ihre direkten Kosten plus die über alle Szenarien gemittelten besten Folgekosten möglichst klein werden. Die Folgekosten Q_s(x) sind selbst wieder das Ergebnis einer Optimierung – ein Problem im Problem.

3.4 Das Beispiel: Server für eine Cloud

Ein Cloud-Anbieter kann an drei Standorten Server aufstellen. Die Entscheidung x = (x_N, x_M, x_S) gibt an, ob Nord, Mitte und Süd geöffnet werden (1) oder nicht (0). Vier Kundenregionen R1 bis R4 brauchen im kommenden Jahr Rechenleistung, gemessen in Einheiten. Alle Beträge sind in Tausend Euro angegeben.

Die Regeln der zweiten Stufe: Jede Region wird als Ganzes genau einem geöffneten Standort zugeordnet oder ganz an die fremde Cloud abgegeben. Ein Standort darf nicht mehr Einheiten übernehmen, als seine Kapazität erlaubt. Die Kosten sind Bedarf mal Kosten je Einheit. Weil die fremde Cloud immer einspringen kann, gibt es zu jeder ersten Entscheidung eine zulässige Reaktion; man spricht von vollständigem Rekurs.

Die Regel „als Ganzes“ macht die zweite Stufe ganzzahlig, und sie hat Folgen. In der Spitze braucht jede Region 4 Einheiten. Mitte hat nur 3 Einheiten Kapazität und kann deshalb in der Spitze keine einzige Region übernehmen. Süd hat 6 Einheiten, kann aber nur eine Region zu 4 Einheiten aufnehmen; die übrigen 2 Einheiten bleiben ungenutzt. Diese Effekte sieht die LP-Relaxation nicht, die Regionen beliebig teilen darf.

Erst wird über die Standorte entschieden, dann zeigt sich das Szenario, dann werden die Regionen zugeordnet. Die erste Entscheidung muss für beide Szenarien zugleich taugen. Datenbasis: Rechenbeispiel dieses Dossiers.

Im Beispiel ist die beste Wahl, Nord und Süd zu öffnen. Das kostet 27 für die Standorte und im Erwartungswert 50,5 für die zweite Stufe, zusammen 77,5. Diese Antwort ist hier nur deshalb bekannt, weil man bei acht Kombinationen alle durchrechnen kann. Das Benders-Verfahren soll sie finden und beweisen, ohne alle Kombinationen zu prüfen.

3.5 Die extensive Form: alles auf einmal

Man kann das zweistufige Problem auch als ein einziges großes MIP aufschreiben. Dazu bekommt jedes Szenario eine eigene Kopie der Variablen der zweiten Stufe, und alle Kopien hängen an derselben ersten Entscheidung. Diese Fassung heißt extensive Form oder deterministisches Äquivalent.

Im Beispiel hat sie 3 Variablen der ersten Stufe und je Szenario 16 binäre Zuordnungsvariablen (vier Regionen mal vier Möglichkeiten), zusammen 35 – für jeden Solver eine Kleinigkeit. Mit 1000 Szenarien wären es schon über 16 000, mit mehreren Stufen oder nichtlinearen Zusammenhängen wird es schnell unlösbar. Die Zahl der Variablen wächst zwar nur linear mit den Szenarien, die Schwierigkeit eines MIP aber oft viel schneller.

Jede Zeile steht für die Nebenbedingungen eines Szenarios. Nur die Spalte der ersten Stufe reicht durch alle Zeilen. Wer sie festhält, erhält unabhängige Blöcke – die Teilprobleme der Benders-Dekomposition. Datenbasis: Darstellung dieses Dossiers.

3.6 Die Struktur, die man ausnutzen kann

Schaut man auf die Nebenbedingungen der extensiven Form, sieht man ein typisches Muster: Jedes Szenario bildet einen eigenen Block, und nur die Variablen der ersten Stufe tauchen in allen Blöcken auf. Man nennt sie die verbindenden oder komplizierenden Variablen. Hält man sie fest, zerfällt das große Problem in S kleine, voneinander unabhängige Probleme, die man einzeln und sogar gleichzeitig auf mehreren Rechnern lösen kann. Diese Beobachtung ist der Ausgangspunkt der Benders-Dekomposition.

Alles dreht sich um eine Funktion, die niemand als Formel kennt: die Folgekosten jeder ersten Entscheidung. Benders nähert sie von unten durch Geraden an. Ob das gelingt, hängt an einer Eigenschaft namens Konvexität.

4.1 Was die Wertfunktion misst

Die Wertfunktion Q_s(x) ordnet jeder ersten Entscheidung x die bestmöglichen Kosten der zweiten Stufe im Szenario s zu. Man kann sie nicht hinschreiben, sondern nur Punkt für Punkt ausrechnen: Für jedes x löst man das Problem der zweiten Stufe. Im Beispiel ergibt das folgende Tabelle.

Ein Beispiel zum Nachrechnen: Sind Nord und Süd offen, übernimmt Nord im ruhigen Szenario die Regionen R1 und R2 (2 · 1 + 2 · 2 = 6) und Süd die Regionen R3 und R4 (2 · 2 + 3 · 1 = 7). Das ergibt Q_ruhig(1, 0, 1) = 13. In der Spitze passt in Nord nur R1 (4 Einheiten, Kosten 4), in Süd nur R4 (Kosten 4); R2 und R3 gehen mit je 4 · 10 = 40 an die fremde Cloud: zusammen 88. Nicht genannte Regionen gehen in der Tabelle immer an die fremde Cloud.

4.2 Warum man die Wertfunktion nicht einfach tabelliert

Bei drei Standorten sind es acht Zeilen, also acht Rechnungen je Szenario. Bei zehn Standorten wären es 1024, bei fünfzig mehr als eine Billiarde – und jede Zeile ist ein eigenes MIP. Die Wertfunktion vollständig zu kennen, ist also hoffnungslos. Man braucht eine Näherung, die mit wenigen Rechnungen auskommt und trotzdem verlässlich ist. „Verlässlich“ heißt hier: Sie darf die Folgekosten nie überschätzen, sonst wäre die untere Schranke falsch.

4.3 Cuts: Geraden unter der Wertfunktion

Die einfachste verlässliche Näherung ist eine Gerade – bei mehreren Variablen genauer eine Ebene –, die nirgends über der Wertfunktion liegt. Mit einer neuen Variable θ_s für die geschätzten Folgekosten schreibt man sie als

Die Zahlen a = (a₁, …, a_n) sind die Steigungen, b ist der Achsenabschnitt. Eine solche Ungleichung heißt Cut (englisch für Schnitt), weil sie im Masterproblem einen Teil der bisher erlaubten Werte von θ_s abschneidet. Zwei Eigenschaften sind entscheidend:

Ein Beispiel mit Zahlen aus der Tabelle: Der Cut θ_ruhig ≥ 27 − 16 x_N ergibt bei geschlossenem Nord den Wert 27 und bei offenem Nord den Wert 11. Ein Blick in die Tabelle zeigt: Alle Zeilen mit x_N = 0 haben mindestens 27, alle mit x_N = 1 mindestens 11. Der Cut ist also gültig. Er ist straff bei (0, 1, 1), wo die Folgekosten genau 27 betragen, und zusätzlich bei (1, 1, 1) mit genau 11. Woher solche Cuts kommen, zeigen die Kapitel 6 bis 8.

Mehrere Cuts zusammen ergeben eine Treppe aus Ebenen: Für jedes x zählt der höchste Cut. Je mehr gute Cuts man sammelt, desto näher kommt diese Treppe der wahren Wertfunktion – jedenfalls dort, wo es darauf ankommt.

4.4 Konvex oder nicht konvex

Eine Funktion heißt konvex, wenn die Verbindungsstrecke zwischen zwei Punkten ihres Graphen nie unter dem Graphen verläuft – anschaulich: eine Schüssel ohne Dellen. Ist die zweite Stufe ein lineares Programm, ist die Wertfunktion konvex. Dann gilt etwas Bequemes: Jede Tangente liegt komplett unter der Funktion, ist also ein gültiger Cut, und aus genügend vielen Tangenten lässt sich die Funktion beliebig genau zusammensetzen.

Ist die zweite Stufe ganzzahlig, wird die Wertfunktion im Allgemeinen nichtkonvex: Sie springt, hat Stufen und Dellen. Eine Tangente an einer Stelle kann an anderer Stelle durch die Funktion hindurchschneiden – ein solcher Cut wäre ungültig. Das Schaubild zeigt einen Schnitt durch das Beispiel: Süd ist offen, Mitte geschlossen, und Nord wird schrittweise von 0 auf 1 „geöffnet“.

Schnitt durch das Beispiel: Süd ist offen, Mitte zu, Nord wird von 0 bis 1 „geöffnet“. An den binären Punkten 0 und 1 treffen sich wahre Wertfunktion und konvexe Hülle; die LP-Relaxation bleibt bei 0 um 7 darunter, und der LP-Cut berührt nur sie. Datenbasis: eigene Berechnung.

Drei Kurven sind zu sehen. Die wahre Wertfunktion ist eine Treppe: Solange Nord nicht ganz offen ist, darf keine Region dorthin, die Kosten bleiben bei 47; erst bei x_N = 1 fallen sie auf 13. Die LP-Relaxation darf Regionen teilen und auch einen „halb offenen“ Standort halb nutzen; sie liegt deshalb überall darunter, schon bei x_N = 0 mit 40 statt 47. Dazwischen liegt die konvexe Hülle: die höchste konvexe Funktion, die noch unter der Treppe bleibt – hier einfach die Strecke von 47 nach 13.

4.5 Die konvexe Hülle und die Ecken des Würfels

Jeder gültige Cut ist eine Ebene unter der Wertfunktion. Eine Ebene ist konvex, also kann kein gültiger Cut je über die konvexe Hülle hinausragen. Die konvexe Hülle ist damit das Beste, was Cuts überhaupt erreichen können. Bei einer nichtkonvexen Funktion klafft dazwischen an manchen Stellen eine Lücke, die kein Cut schließen kann – im Schaubild etwa bei x_N = 0,5: Die Treppe steht bei 47, die Hülle bei 30.

Für binäre erste Stufen gibt es aber eine glückliche Fügung. Die binären Punkte sind die Ecken des Würfels [0, 1]ⁿ. Eine Ecke lässt sich nicht als Mischung anderer Punkte des Würfels schreiben. Deshalb stimmen konvexe Hülle und Wertfunktion an jeder Ecke überein: Im Schaubild treffen sich alle Kurven außer der LP-Relaxation bei 0 und bei 1. Weil das Masterproblem nur binäre Punkte vorschlagen darf, reicht das. An jedem binären Punkt gibt es einen gültigen Cut, der dort straff ist.

Das Benders-Verfahren ist ein Gespräch zwischen zwei Ebenen: Das Masterproblem schlägt vor, die Teilprobleme antworten, und jede Antwort wird als Cut festgehalten. Zwei Schranken zeigen in jeder Runde, wie weit man noch vom Ziel entfernt ist.

5.1 Die Idee: Unbekanntes durch Variablen ersetzen

Jacques F. Benders, Mathematiker im Laboratorium von Shell in Amsterdam, entwickelte das Verfahren in seiner Doktorarbeit von 1960 und veröffentlichte es 1962 in der Zeitschrift Numerische Mathematik. Seine Idee: Man ersetzt die unbekannte Wertfunktion Q_s(x) im Ziel durch eine Variable θ_s und beschränkt diese von unten durch Cuts. Das entstehende Problem heißt Masterproblem:

Am Anfang kennt das Masterproblem noch keinen Cut. Man gibt ihm eine einfache untere Grenze mit, im Beispiel θ_s ≥ 0, denn Kosten sind nie negativ. Das Masterproblem glaubt dann zunächst, Folgekosten gäbe es nicht – und schlägt entsprechend naiv vor. Aus jeder Bewertung lernt es dazu.

5.2 Der Kreislauf

In jeder Runde schlägt der Master eine erste Entscheidung vor. Die Teilprobleme bewerten sie, daraus folgt eine obere Schranke, und jedes liefert einen Cut zurück. Mit den Cuts wird der Master genauer, seine untere Schranke steigt. Datenbasis: Darstellung dieses Dossiers.

Eine Runde, in Fachartikeln Iteration genannt, läuft so ab:

1. Master lösen. Das Masterproblem liefert einen Vorschlag x^k und seinen Optimalwert. Dieser Wert ist eine untere Schranke für das Gesamtproblem.
2. Vorschlag bewerten. Für jedes Szenario wird das Teilproblem bei x = x^k gelöst; das ergibt Q_s(x^k). Die echten Kosten des Vorschlags, c^⊤x^k + Σ p_s Q_s(x^k), sind eine obere Schranke. Man merkt sich die beste bisher.
3. Prüfen. Ist die Lücke zwischen bester oberer und aktueller unterer Schranke klein genug, endet das Verfahren. Der beste Vorschlag ist dann bewiesen gut genug.
4. Lernen. Für jedes Szenario wird ein Cut erzeugt, der möglichst bei x^k straff ist, und dem Masterproblem hinzugefügt.
5. Wiederholen. Zurück zu Schritt 1.

5.3 Warum die Schranken stimmen

Die untere Schranke: Solange jeder Cut gültig ist, unterschätzt jedes θ_s die wahren Folgekosten oder trifft sie genau. Das Masterproblem ist damit eine Relaxation des echten Problems und kann dessen Optimalwert nicht übersteigen. Woher die Cuts stammen, ist dabei gleichgültig – es kommt allein auf ihre Gültigkeit an.

Die obere Schranke: Jeder Vorschlag x^k ist eine echte, umsetzbare Entscheidung. Seine tatsächlichen Kosten kann das Optimum nicht übertreffen.

Mit jedem Cut wird das Masterproblem strenger, die untere Schranke steigt oder bleibt gleich. Die beste obere Schranke fällt oder bleibt gleich. Die Lücke wird also nie größer.

5.4 Warum das Verfahren endet

Bei binärer erster Stufe gibt es nur endlich viele mögliche Vorschläge. Angenommen, an jedem Vorschlag x^k wird für jedes Szenario ein Cut erzeugt, der dort straff ist. Schlägt das Masterproblem denselben Punkt später ein zweites Mal vor, dann kennt es dessen Folgekosten bereits exakt. Sein Optimalwert ist dann gleich den echten Kosten dieses Punktes – und die sind mindestens so groß wie die beste obere Schranke. Untere und obere Schranke stimmen überein, das Verfahren endet.

Jeder Punkt wird also höchstens einmal „neu“ vorgeschlagen, und nach höchstens so vielen Runden, wie es Punkte gibt, plus einer weiteren ist Schluss. Das ist eine Garantie für den schlimmsten Fall; in der Praxis braucht ein gutes Verfahren nur einen winzigen Bruchteil davon. Die Voraussetzung ist aber wesentlich: Ohne straffe Cuts gibt es diese Garantie nicht. Kapitel 6 zeigt am Beispiel, was dann passiert.

5.5 Varianten und Namen

Ist die zweite Stufe ein lineares Programm, liefert die Dualität die Cuts gleichsam gratis mit. Bei ganzzahliger zweiter Stufe funktioniert das nicht mehr: Die Cuts bleiben gültig, aber sie berühren nicht – und das Verfahren bleibt stecken.

6.1 Der Normalfall: lineare zweite Stufe

Ist das Teilproblem ein LP, löst man es bei x und liest die Schattenpreise π der Nebenbedingungen ab, die x enthalten. Sie geben an, wie stark sich die Folgekosten ändern, wenn man x ein wenig verschiebt. Daraus entsteht der klassische Benders-Cut

Er ist eine Tangente an die Wertfunktion im Punkt x. Weil die Wertfunktion eines LP konvex ist, liegt diese Tangente überall darunter: Der Cut ist gültig und bei x straff. Ein einziger Solve des Teilproblems liefert beides, Funktionswert und Steigung. Das ist der Grund, warum Benders für lineare zweite Stufen so gut funktioniert.

Im Beispiel bedeutet ein Schattenpreis von −66 für Nord: In der Welt der LP-Relaxation würde ein „ein wenig mehr geöffnetes“ Nord die Folgekosten mit einer Rate von 66 senken. Negative Steigungen sind hier normal, denn ein zusätzlicher Standort senkt die Folgekosten.

6.2 Ganzzahlige zweite Stufe: Es fehlt der Dual

Ist das Teilproblem ein MIP, gibt es keine Schattenpreise, die die Wertfunktion exakt beschreiben. Der naheliegende Ausweg: Man löst statt des MIP seine LP-Relaxation und nimmt deren Schattenpreise. Der Cut ist dann eine Tangente an die Wertfunktion der Relaxation. Weil diese überall unter der wahren Wertfunktion liegt, ist der Cut gültig. Er ist aber im Allgemeinen nicht straff: Er berührt die tiefer liegende LP-Kurve, nicht die wahre Treppe.

Im Beispiel wird das an zwei Stellen deutlich:

Am ersten Fall lässt es sich nachrechnen. In der Spitze nimmt Nord R1 auf (Kosten 4) und Süd R4 (Kosten 4). Süd hätte noch 2 Einheiten frei, aber R3 braucht 4 und ist unteilbar – also gehen R2 und R3 für je 40 an die fremde Cloud: 88. Darf man R3 teilen, gehen 2 Einheiten für 2 · 2 = 4 nach Süd und nur 2 Einheiten für 20 an die fremde Cloud; zusammen mit R2 sind es 4 + 4 + 4 + 20 + 40 = 72. Die LP-Relaxation unterschätzt die Folgekosten um 16.

6.3 Was dann passiert: Das Verfahren bleibt stecken

Mit Cuts aus der LP-Relaxation steigt die untere Schranke im Beispiel nur bis 69,5. Danach schlägt das Masterproblem immer wieder denselben Punkt vor – Nord und Süd –, und der neue Cut ist derselbe wie beim letzten Mal. Er lehrt das Masterproblem nichts Neues, weil er die echten Folgekosten an diesem Punkt (13 und 88) nicht erreicht, sondern nur die der Relaxation (13 und 72).

Die beste Lösung ist schon in Runde 2 gefunden – aber das Verfahren kann nicht beweisen, dass sie die beste ist. Es bleibt eine Lücke von 8, rund zehn Prozent. Der Satz aus Kapitel 5.4 greift nicht, weil seine Voraussetzung fehlt: Die Cuts sind am Vorschlag nicht straff.

6.4 Frühere Auswege

Bevor Lagrange-Cuts verbreitet waren, gab es andere Antworten auf dieses Problem. Das ganzzahlige L-shaped-Verfahren von Laporte und Louveaux (1993) nutzt aus, dass die erste Stufe binär ist, und baut Cuts, die am Vorschlag straff sind – sie geben aber anderswo oft nur grobe Auskunft und lassen sich nur mit einer bekannten unteren Grenze der Folgekosten bilden. Andere Ansätze verschärfen die LP-Relaxation der Teilprobleme mit Schnittebenen, bis sie der Ganzzahligkeit näher kommt. Die duale Zerlegung von Carøe und Schultz (1999) gibt jedem Szenario eine eigene Kopie der ersten Entscheidung und relaxiert die Bedingung, dass alle Kopien übereinstimmen. Die Lagrange-Cuts des nächsten Kapitels sind damit eng verwandt: Chen und Luedtke zeigten 2022, dass alle Lagrange-Cuts zusammen genau die Schranke dieser dualen Zerlegung erreichen.

Ein kleiner Trick macht ganzzahlige Teilprobleme zugänglich: Man gibt dem Teilproblem eine eigene Kopie der ersten Entscheidung und verlangt nicht mehr, dass sie mit dem Original übereinstimmt – sondern stellt Abweichungen in Rechnung. Heraus kommen Cuts, die für jeden Preis gültig sind.

7.1 Die Idee der Lagrange-Relaxation

Joseph-Louis Lagrange führte 1788 in seiner Mécanique analytique Multiplikatoren ein, um Nebenbedingungen in der Mechanik zu behandeln. In der ganzzahligen Optimierung wurde daraus ab etwa 1970 ein Standardwerkzeug: Michael Held und Richard Karp nutzten es 1970/71 für das Problem des Handlungsreisenden, Arthur Geoffrion prägte 1974 den Namen Lagrange-Relaxation.

Das Prinzip: Eine störende Nebenbedingung wird gestrichen und stattdessen mit einem Preis, dem Lagrange-Multiplikator, in die Zielfunktion übernommen. Wer sie verletzt, zahlt; wer sie übererfüllt, wird belohnt. Für jeden beliebigen Preis ist das Ergebnis eine untere Schranke für das ursprüngliche Problem. Die Kunst besteht darin, den Preis so zu wählen, dass diese Schranke möglichst hoch ausfällt.

7.2 Der Trick mit der Kopie

Für die Benders-Dekomposition wendet man das auf das Teilproblem an. Zunächst bekommt es eine eigene Kopie z der ersten Entscheidung. Die Kopie darf zwischen 0 und 1 liegen und muss mit x übereinstimmen:

An der Wertfunktion ändert das nichts – die Kopie ist ja gleich dem Original. Aber die Verbindung zwischen Master und Teilproblem steckt jetzt in einer einzigen, übersichtlichen Gleichung: z = x. Alle schwierigen Bedingungen, Ganzzahligkeit und Nichtkonvexität, bleiben im Teilproblem. Nun relaxiert man nur diese eine Gleichung, mit einem Multiplikator μ = (μ₁, …, μ_n):

In Worten: Das Teilproblem darf seine Kopie z jetzt frei wählen, unabhängig davon, was der Master entschieden hat. Dafür wird ihm für jeden Standort der Betrag μ_j z_j von den Kosten abgezogen. Der Wert v_s(μ) ist das Ergebnis dieses gelockerten Problems. Ihn zu berechnen kostet einen Solve – ein MIP von der Größe des ursprünglichen Teilproblems.

7.3 Der Lagrange-Cut und warum er immer gilt

Der Lagrange-Cut zum Multiplikator μ lautet

Er ist eine Ebene mit Steigung μ und Achsenabschnitt v_s(μ). Seine Gültigkeit lässt sich in drei Schritten zeigen. Man nehme irgendeine zulässige Lösung (y, z) des echten Teilproblems bei x; für sie gilt z = x. Dann ist

Die Gleichheit gilt, weil μ^⊤z und μ^⊤x sich wegheben. Die Ungleichung gilt, weil (y, z) auch im gelockerten Problem erlaubt ist und dessen Minimum v_s(μ) nicht unterschreiten kann. Das gilt für jede zulässige Lösung, also auch für die beste: Q_s(x) ≥ μ^⊤x + v_s(μ).

7.4 Eine anschauliche Deutung: Miete für Standorte

Im Beispiel sind die sinnvollen Multiplikatoren negativ. Man kann −μ_j als Miete r_j lesen, die das Teilproblem für die Nutzung von Standort j zahlen muss. Das gelockerte Teilproblem lautet dann: „Nutze, welche Standorte du willst – ganz gleich, ob der Master sie geöffnet hat –, zahle aber für jeden genutzten Standort seine Miete.“ v_s(μ) sind die besten Gesamtkosten aus Zuordnung und Miete.

Der Cut θ_s ≥ v_s(μ) − Σ r_j x_j sagt dann: „Für jeden Standort, den der Master wirklich öffnet, bekommst du die Miete zurück.“ Ist die Miete zu niedrig, nutzt das Teilproblem auch Standorte, die der Master geschlossen hat, und der Cut unterschätzt die Folgekosten. Ist sie hoch genug, verzichtet es darauf, und der Cut trifft.

7.5 Ein Lagrange-Cut von Hand

Betrachten wir den Vorschlag „Mitte und Süd offen, Nord zu“, also x = (0, 1, 1), im ruhigen Szenario. Die wahren Folgekosten sind 27. Wir verlangen Miete r nur für Nord; Mitte und Süd sind mietfrei (μ_M = μ_S = 0). Dann kommen für das gelockerte Teilproblem zwei Pläne in Frage:

Das Teilproblem nimmt den billigeren Plan, also ist v(r) = min(11 + r, 27), und der Cut lautet θ_ruhig ≥ v(r) − r · x_N. Bei x ist x_N = 0, der Cut hat dort also den Wert v(r).

Dieses kleine Beispiel enthält schon die drei Lehren der nächsten Kapitel: Jede Miete liefert einen gültigen Cut. Erst ab einer bestimmten Miete ist er straff. Und unter den straffen Cuts gibt es bessere und schlechtere.

7.6 Straff an binären Punkten

Den besten Multiplikator für einen Punkt x findet man, indem man die Höhe des Cuts an diesem Punkt maximiert:

Dieses Problem heißt Lagrange-Dual. Sein Optimalwert ist genau der Wert der konvexen Hülle der Wertfunktion an der Stelle x – höher kann nach Kapitel 4.5 kein Cut kommen, und mit dem besten Multiplikator wird diese Höhe erreicht. An binären Punkten ist die konvexe Hülle gleich der Wertfunktion. Daraus folgt der zentrale Satz, den Zou, Ahmed und Sun 2019 für ihr Verfahren SDDiP bewiesen haben: An einem binären Punkt berührt der Lagrange-Cut mit dem besten Multiplikator die Wertfunktion. Damit ist die Voraussetzung aus Kapitel 5.4 erfüllt, und das Benders-Verfahren endet nach endlich vielen Runden – auch mit ganzzahligen und nichtkonvexen Teilproblemen.

7.7 Der verstärkte Benders-Cut

Den besten Multiplikator zu finden ist aufwendig (Kapitel 8). Eine billige Abkürzung liegt nahe: Man nimmt als Multiplikator einfach die Schattenpreise der LP-Relaxation – den klassischen Benders-Cut – und berechnet nur den Achsenabschnitt v_s(μ) neu, mit einem einzigen ganzzahligen Solve. Das Ergebnis heißt verstärkter Benders-Cut (englisch strengthened Benders cut). Er ist gültig, weil jeder Lagrange-Cut gültig ist, und immer mindestens so gut wie der LP-Cut mit derselben Steigung.

Oft ist er sogar straff. Im Beispiel liefert die LP-Relaxation am Punkt „Nord, Süd offen“ in der Spitze die Steigung −132 für Mitte und den Achsenabschnitt 72. Der neu berechnete Achsenabschnitt ist 88 – und der verstärkte Cut θ ≥ 88 − 132 x_M ist bei (1, 0, 1) straff. Am Punkt „Mitte, Süd offen“ im ruhigen Szenario dagegen ist die LP-Steigung für Nord −8: Das ist genau der Fall „Miete 8“ von oben, und der verstärkte Cut bleibt bei 19 statt 27 stehen. Dann muss man suchen.

7.8 Ungenau gerechnet ist trotzdem gültig

Der Achsenabschnitt v_s(μ) ist das Minimum eines MIP. Bricht man den Solver nach einem Zeitlimit ab, kennt man dieses Minimum vielleicht nicht genau, wohl aber eine gültige untere Schranke dafür (Kapitel 2.5). Setzt man diese Schranke statt v_s(μ) ein, rutscht der Cut ein Stück nach unten – er bleibt gültig, ist aber nicht mehr straff. Hätte der Solver im Beispiel bei Miete 16 nur die Schranke 24 statt 27 erreicht, lautete der Cut θ ≥ 24 − 16 x_N: korrekt, aber um 3 zu niedrig. Solche ungenauen Cuts sind für lineare Teilprobleme seit der Arbeit von Zakeri, Philpott und Ryan (2000) gut untersucht; bei ganzzahligen Teilproblemen sind sie die Regel, sobald Rechenzeit knapp ist. Die Endlichkeitsgarantie aus Kapitel 5.4 gilt für sie aber nicht ohne Weiteres, weil sie die Straffheit voraussetzt.

Der beste Multiplikator ist der Gipfel einer Funktion, die man nur Punkt für Punkt abtasten kann – und jeder Punkt kostet einen Solve. Wie man diesen Gipfel findet und warum das die eigentliche Rechenlast ist, zeigt dieses Kapitel.

8.1 Das Lagrange-Dual als Berglandschaft

Für einen festen Punkt x betrachtet man die Funktion

Sie gibt an, wie hoch der Cut mit Steigung μ am Punkt x liegt. Weil v_s(μ) ein Minimum über viele Pläne ist und jeder Plan linear von μ abhängt, ist L das Minimum vieler Ebenen: eine konkave, stückweise lineare Funktion – ein Dach aus ebenen Flächen mit Kanten, aber ohne Dellen. Konkav heißt: Es gibt keinen falschen Gipfel, jedes lokale Maximum ist auch das globale. Die Schwierigkeit liegt woanders: Man sieht das Dach nicht, man kann nur an einzelnen Stellen messen, und jede Messung ist ein MIP.

Im Beispiel aus Kapitel 7.5 ist das Dach eindimensional und lässt sich vollständig zeichnen: L(r) = min(11 + r, 27). Es steigt mit der Miete an und wird ab r = 16 flach. Mit dem Regler lässt sich die Miete verschieben.

Die Höhe des Cuts am Punkt (0, 1, 1) wächst mit der Miete, bis das Teilproblem auf Nord verzichtet; ab Miete 16 ist der Cut straff. Die Tabelle prüft den Cut an allen acht Punkten: Er ist bei jeder Miete gültig. Datenbasis: eigene Berechnung.

8.2 Die Richtung bergauf kommt gratis mit

Löst man das gelockerte Teilproblem bei einem Multiplikator μ, erhält man neben dem Wert auch die gewählte Kopie z*(μ). Der Vektor

zeigt bergauf: Er ist ein Supergradient der konkaven Funktion L. Die Deutung ist einfach. Nutzt das Teilproblem einen Standort, den der Master geschlossen hat (z*_j = 1, x_j = 0), ist g_j = −1: Man sollte μ_j senken, also die Miete erhöhen. Verzichtet es auf einen Standort, den der Master geöffnet hat (z*_j = 0, x_j = 1), ist g_j = +1: Die Miete ist zu hoch. Stimmen Kopie und Vorschlag überein, ist g = 0 – und man steht auf dem Gipfel.

8.3 Durchgerechnet: drei Schritte zum Gipfel

8.4 Drei Suchverfahren

Alle drei teilen eine Eigenschaft: Jeder Schritt verlangt einen Solve des gelockerten Teilproblems. Man kann die Suche jederzeit abbrechen. Weil jeder Multiplikator einen gültigen Cut ergibt, verwendet man dann einfach den besten bisher gefundenen – gültig, nur vielleicht nicht straff. In der Praxis begrenzt man deshalb die Zahl der Schritte und die Rechenzeit je Solve.

8.5 Was die Suche teuer macht

Eine überschlägige Rechnung zeigt, wo die Rechenzeit bleibt. Bei 100 Szenarien, 20 Suchschritten je Cut und 50 Benders-Runden sind es 100 · 20 · 50 = 100 000 Solves von MIP-Teilproblemen. Der Master selbst fällt daneben kaum ins Gewicht. Chen und Luedtke betonen in ihrer Arbeit von 2022 entsprechend, dass das Erzeugen von Lagrange-Cuts rechnerisch anspruchsvoll ist, und schlagen vor, die Suche zu normieren und die Steigungen auf einen kleinen Raum einzuschränken, der von früheren Benders-Cuts aufgespannt wird. So kommen sie mit weit weniger Schritten zu guten Cuts.

8.6 Viele Gipfel auf gleicher Höhe

Das Dach im Beispiel ist ab Miete 16 flach: Jede Miete von 16 an aufwärts ist optimal, alle liefern bei (0, 1, 1) die Höhe 27. Für den Punkt selbst sind sie gleich gut. Für die übrigen Punkte nicht: Bei offenem Nord ergibt Miete 16 den Wert 11, Miete 40 den Wert −13. Das ist typisch. An binären Punkten ist die Menge der besten Multiplikatoren oft groß, manchmal sogar unbegrenzt, und welche man erwischt, hängt vom Suchverfahren und seinem Startpunkt ab. Ein Bündelverfahren, das beim LP-Multiplikator startet, bleibt in dessen Nähe; im Beispiel ist das die flache, nützliche Lösung mit Miete 16. Gezielt steuern lässt sich die Auswahl mit den Ideen aus Kapitel 10.

Jetzt läuft das ganze Verfahren am Beispiel des Cloud-Anbieters durch – Runde für Runde, mit allen Zahlen. Wir tun dabei so, als kennten wir die Tabelle der Wertfunktion nicht: Das Verfahren erfährt nur die Folgekosten der Punkte, die es selbst vorschlägt.

9.1 Die Spielregeln

9.2 Runde für Runde

9.3 Zum Durchklicken

Das folgende Schaubild zeigt für jede Runde, was der Master über alle acht Entscheidungen weiß. Die Umrisse sind die wahren Gesamtkosten, die gefüllten Säulen die Schätzung des Masters – sie liegt nie darüber. Der Vorschlag der Runde ist hervorgehoben. Über die Schaltflächen lässt sich auch verfolgen, wie dasselbe Verfahren mit LP-Cuts stecken bleibt und wie es mit Cuts nach der Kernpunkt-Regel aus Kapitel 10 schon in Runde 2 endet.

Für jede der acht Entscheidungen zeigt die gefüllte Säule die Schätzung des Masters in dieser Runde, der Umriss die wahren Gesamtkosten. Der Master wählt die niedrigste gefüllte Säule. Die gestrichelten Linien sind untere und beste obere Schranke. Datenbasis: eigene Berechnung.

9.4 Die Schranken im Überblick

In jeder Runde mit Cuts kostet jedes Szenario mindestens einen ganzzahligen Solve für die Bewertung und einen für den Achsenabschnitt; „zusätzlich“ zählt nur die Suchschritte darüber hinaus. Das Schaubild vergleicht den Verlauf der unteren Schranke für drei Arten von Cuts.

Alle drei Verfahren finden die beste Lösung in Runde 2 (obere Schranke 77,5). Beweisen können sie es nur mit straffen Cuts: Lagrange-Cuts nach sechs Runden, Kernpunkt-Cuts nach zwei; LP-Cuts nie. Datenbasis: eigene Berechnung.

Am selben Punkt können viele Cuts gleich straff sein, aber anderswo sehr verschieden viel verraten. Seit 1981 gibt es eine einfache Regel, um unter ihnen zu wählen: Man schaut nicht nur auf den aktuellen Punkt, sondern auf einen Punkt in der Mitte.

10.1 Starke und schwache Cuts

Ein Cut dominiert einen anderen, wenn er überall mindestens so hoch liegt und irgendwo höher. Ein Cut, der von keinem gültigen Cut dominiert wird, heißt Pareto-optimal. Thomas Magnanti und Richard Wong beobachteten 1981, dass die dualen Lösungen der Teilprobleme oft nicht eindeutig sind und dass die Wahl unter ihnen die Zahl der Benders-Runden stark beeinflusst. Bei Lagrange-Cuts tritt dieselbe Mehrdeutigkeit auf, wie Kapitel 8.6 gezeigt hat.

10.2 Die Kernpunkt-Regel von Magnanti und Wong

Ein Kernpunkt ist ein Punkt im Inneren der konvexen Hülle aller erlaubten ersten Entscheidungen – bei drei binären Variablen ohne weitere Einschränkung etwa die Würfelmitte (½, ½, ½). Die Regel lautet: Unter allen Cuts, die am aktuellen Vorschlag straff sind, wähle den, der am Kernpunkt am höchsten liegt. Magnanti und Wong zeigten, dass so gewählte Cuts Pareto-optimal sind. Der Preis ist ein zusätzliches Hilfsproblem je Cut.

Anschaulich: Ein Cut, der in der Mitte hoch liegt, ist eine flache, breit tragende Ebene statt einer steilen Rampe. Er ist am aktuellen Punkt genauso straff, sagt aber auch über die Nachbarschaft etwas Brauchbares.

10.3 Am Beispiel: zwei Runden statt sechs

In Runde 1 liegt der Vorschlag bei (0, 0, 0). Die Suche nahe am LP-Multiplikator lieferte die steilen Mieten (66, 73, 69). Wählt man stattdessen unter allen straffen Cuts den, der bei (½, ½, ½) am höchsten liegt, ergeben sich die Mieten (34, 21, 43) im ruhigen Szenario und (36, 0, 36) in der Spitze. Die Tabelle vergleicht beide Cuts an allen acht Punkten mit der wahren Wertfunktion.

Der Unterschied ist verblüffend. Der steile Cut ist nur bei (0, 0, 0) straff. Der Kernpunkt-Cut ist im ruhigen Szenario an sechs von acht Punkten straff und in der Spitze sogar an allen acht. Insbesondere kennt der Master nach nur einer Runde die Folgekosten des Optimums (1, 0, 1) exakt: 13 und 88. In Runde 2 schlägt er (1, 0, 1) vor, untere und obere Schranke treffen sich bei 77,5, und das Verfahren endet.

In der Sprache der Mieten hat die Kernpunkt-Regel etwas sehr Natürliches gewählt: Jede Miete ist genau so hoch wie die Ersparnis, die der Standort allein bringt. Nord allein senkt die ruhigen Folgekosten von 90 auf 56, also um 34; Mitte um 21; Süd um 43. In der Spitze sparen Nord und Süd je 36, Mitte nichts.

10.4 Kernpunkte in der Praxis

Einen Punkt im Inneren der konvexen Hülle zu kennen, ist bei komplizierten erlaubten Mengen X selbst nicht leicht. Nikolaos Papadakos schlug 2008 zwei praktische Verbesserungen vor: eine unabhängige Fassung des Verfahrens von Magnanti und Wong, die nicht mehr an die Lösung des Teilproblems am aktuellen Vorschlag gebunden ist, und den Nachweis, dass für mehrere Anwendungen statt eines echten Kernpunkts auch andere Punkte genügen. Verbreitet ist seither, den Bezugspunkt im Lauf des Verfahrens aus den bisherigen Vorschlägen des Masters fortzuschreiben – etwa als Mischung aus altem Bezugspunkt und neuem Vorschlag oder als laufenden Mittelwert aller Vorschläge.

10.5 Übertragen auf Lagrange-Cuts

Bei Lagrange-Cuts lässt sich der Gedanke direkt übertragen. Statt die Höhe des Cuts am Vorschlag x^k zu maximieren, maximiert man sie an einem anderen Punkt x̂, der auch gebrochen sein darf:

Der so gewonnene Cut berührt die konvexe Hülle der Wertfunktion an der Stelle x̂ und trägt deshalb in deren Umgebung weit. Er muss aber am aktuellen Vorschlag nicht straff sein. Weil die Endlichkeitsgarantie aus Kapitel 5.4 straffe Cuts an den Vorschlägen verlangt, ergänzt man in solchen Verfahren bei Bedarf einen zweiten, am Vorschlag straffen Cut. In Fachartikeln wird der Punkt x̂, an dem das Lagrange-Dual maximiert wird, unterschiedlich benannt – als Kernpunkt, Referenzpunkt oder, in manchen Arbeiten, als Anker.

10.6 Weitere Beschleuniger

Das kleine Beispiel löst jeder Solver in Sekundenbruchteilen auch ohne Zerlegung. Ihren Wert zeigen Benders-Verfahren mit Lagrange-Cuts erst bei Problemen, an denen die extensive Form scheitert: bei vielen Szenarien, vielen Stufen und nichtkonvexen Zusammenhängen.

11.1 Mehrstufige Probleme

Viele Planungen laufen über mehrere Perioden: Ein Wasserkraftbetreiber entscheidet jede Woche neu, wie viel Wasser er abläuft, und erfährt danach den Zufluss der nächsten Woche. Jede Stufe ist dann Teilproblem der vorigen und Master der nächsten. Die Zahl der Pfade durch den Szenariobaum wächst exponentiell mit der Zahl der Stufen; schon zehn Stufen mit je zehn Möglichkeiten ergeben zehn Milliarden Pfade.

11.2 Nichtkonvexe Probleme

Noch schwieriger wird es, wenn die Teilprobleme nichtlinear und nichtkonvex sind, etwa durch physikalische Zusammenhänge in Strom- und Gasnetzen. Christian Füllner und Steffen Rebennack stellten 2022 die nichtkonvexe verschachtelte Benders-Zerlegung vor. Sie ersetzt nichtlineare Terme durch stückweise lineare Näherungen, die schrittweise verfeinert werden, stellt die Zustandsvariablen binär dar und erzeugt Lagrange-Cuts; eine Regularisierung stabilisiert das Verfahren. Es erreicht in endlich vielen Schritten eine Lösung, die bis auf eine vorgegebene Toleranz optimal ist. Auch hier ist das Erzeugen der Lagrange-Cuts der Engpass.

11.3 Wie Verfahren verglichen werden

Für die Forschung gibt es öffentliche Testsammlungen, etwa die SIPLIB mit Problemen der stochastischen ganzzahligen Optimierung. Darin sind die SSLP-Probleme nach Ntaimo und Sen (2005) enthalten: Server werden an möglichen Standorten aufgestellt (erste Stufe, binär), danach werden Kunden zugeordnet (zweite Stufe, gemischt-binär). Die Namen folgen dem Muster SSLP_m.n.s mit m Standorten, n Kunden und s Szenarien. Das Beispiel dieses Dossiers ist eine Miniatur solcher Probleme.

Typische Kennzahlen in Fachartikeln sind:

11.4 Offene Fragen der Forschung

Ein jüngerer Forschungszweig verbindet Zerlegungsverfahren mit maschinellem Lernen, etwa um Dualwerte, gute Startpunkte oder ganze Cuts vorherzusagen und so Rechenzeit zu sparen. Wie gut solche Ansätze funktionieren und welche Garantien dabei erhalten bleiben, ist Gegenstand laufender Forschung.

Fachartikel zu Benders-Verfahren und Lagrange-Cuts verwenden eine dichte, weitgehend einheitliche Schreibweise. Die beiden Tabellen übersetzen Symbole und typische Wendungen und verweisen auf das Kapitel, das sie erklärt.

12.1 Symbole

12.2 Typische Wendungen

Von Lagranges Multiplikatoren bis zu den Lagrange-Cuts der Gegenwart: die wichtigsten Schritte der Methoden, die in diesem Dossier vorkommen.

Branch-and-Bound

Grundverfahren für ganzzahlige Programme: Das Problem wird schrittweise in Fälle aufgeteilt, Fälle mit zu schlechter unterer Schranke werden verworfen.

Bündelverfahren

Verfahren zur Maximierung nichtglatter konkaver Funktionen wie des Lagrange-Duals; sammelt Messungen als Ebenen und bleibt durch einen Strafterm nahe am bisher besten Punkt.

Cut

Lineare Ungleichung θ_s ≥ a^⊤x + b, die die Folgekosten im Masterproblem von unten abschätzt.

Dualität

Zu jedem Optimierungsproblem gehört ein duales Problem über Preise der Nebenbedingungen; es liefert untere Schranken, bei linearen Programmen sogar den exakten Wert.

Erste Stufe

Die Entscheidungen, die vor dem Eintreten des Zufalls endgültig getroffen werden.

Erwartungswert

Mit den Wahrscheinlichkeiten gewichteter Durchschnitt über alle Szenarien.

Extensive Form

Das gesamte stochastische Problem als ein einziges großes Optimierungsproblem, mit einer Kopie der zweiten Stufe je Szenario; auch deterministisches Äquivalent.

Gemischt-ganzzahliges Programm

Optimierungsproblem mit linearen Bedingungen, in dem ein Teil der Variablen ganzzahlig sein muss (MIP).

Kernpunkt

Punkt im Inneren der konvexen Hülle der erlaubten ersten Entscheidungen; dient bei Magnanti und Wong zur Auswahl Pareto-optimaler Cuts.

Konvex

Eine Funktion ist konvex, wenn jede Verbindungsstrecke zweier Punkte ihres Graphen nicht unter dem Graphen liegt; anschaulich eine Schüssel ohne Dellen.

Konvexe Hülle

Bei einer Funktion: die höchste konvexe Funktion, die nirgends über ihr liegt. Kein Cut kann sie übersteigen.

Lagrange-Cut

Cut θ_s ≥ μ^⊤x + v_s(μ) aus der Lagrange-Relaxation der Kopiergleichung z = x; gültig für jedes μ.

Lagrange-Dual

Die Aufgabe, den Multiplikator so zu wählen, dass die Schranke der Lagrange-Relaxation an einem Punkt möglichst hoch liegt; eine konkave, stückweise lineare Maximierung.

Lagrange-Multiplikator

Preis, mit dem eine gestrichene Nebenbedingung in die Zielfunktion übernommen wird; bei Lagrange-Cuts zugleich deren Steigung.

Lagrange-Relaxation

Eine störende Nebenbedingung wird gestrichen und mit einem Preis in die Zielfunktion übernommen; das Ergebnis ist für jeden Preis eine untere Schranke.

Lineares Programm

Optimierungsproblem mit linearer Zielfunktion und linearen Bedingungen und reellen Variablen (LP); auch in großer Dimension effizient lösbar.

Lücke

Differenz zwischen bester oberer und unterer Schranke, absolut oder relativ angegeben.

Masterproblem

Problem der ersten Stufe im Benders-Verfahren, in dem die Folgekosten durch Variablen θ_s und Cuts ersetzt sind.

Multi-Cut

Benders-Variante mit einer Schätzvariablen und einem Cut je Szenario statt eines gemittelten Cuts.

Pareto-optimaler Cut

Gültiger Cut, den kein anderer gültiger Cut überall erreicht und irgendwo übertrifft.

Relaxation

Gelockerte Fassung eines Problems mit weniger strengen Bedingungen; ihr Optimalwert ist eine untere Schranke.

Schattenpreis

Duale Variable einer Nebenbedingung: Änderung des Optimalwerts, wenn ihre rechte Seite um eine Einheit wächst.

SDDP

Stochastische duale dynamische Programmierung (1991): Benders-artiges Verfahren für mehrstufige Probleme, das Stichproben von Pfaden durchläuft; SDDiP ist die ganzzahlige Erweiterung mit Lagrange-Cuts.

Solver

Software, die Optimierungsprobleme löst, etwa Gurobi, CPLEX, SCIP oder HiGHS. Ein einzelner Aufruf heißt in Fachartikeln oft „Solve“.

Stochastische Optimierung

Optimierung unter Unsicherheit, bei der der Zufall durch Wahrscheinlichkeiten oder Szenarien beschrieben wird; zweistufig, wenn auf eine erste Entscheidung genau eine Reaktion folgt.

Straff

Ein Cut ist straff an einem Punkt, wenn er dort den Wert der Wertfunktion genau erreicht.

Supergradient

Richtung, in der eine konkave, nicht überall glatte Funktion ansteigt; beim Lagrange-Dual der Vektor x − z*(μ).

Szenario

Eine mögliche Ausprägung der unsicheren Daten, mit einer Wahrscheinlichkeit versehen.

Ungenauer Cut

Cut, dessen Achsenabschnitt nur eine untere Schranke des exakten Werts ist, etwa nach einem Zeitlimit; gültig, aber schwächer.

Verstärkter Benders-Cut

Lagrange-Cut mit der Steigung des klassischen LP-Cuts und einem ganzzahlig berechneten Achsenabschnitt; kostet einen zusätzlichen Solve.

Wertfunktion

Funktion Q_s(x), die jeder ersten Entscheidung die besten Kosten der zweiten Stufe im Szenario s zuordnet.

Zertifikat

Nachweis der Lösungsgüte durch eine obere und eine untere Schranke; bei Lücke null ein Beweis der Optimalität.

Zweite Stufe

Die Reaktion auf den eingetretenen Zufall, im Fachjargon Rekurs; ihre besten Kosten beschreibt die Wertfunktion.

Die Darstellung folgt den Standardwerken und Originalarbeiten des Gebiets. Das Rechenbeispiel wurde für dieses Dossier entworfen und vollständig nachgerechnet; seine Zahlen stammen nicht aus einer Veröffentlichung.

Originalarbeiten und Übersichten online

• Wikipedia: Benders decomposition
• Wikipedia: Jacques F. Benders
• Benders: Partitioning procedures for solving mixed-variables programming problems (Nachdruck in Computational Management Science, 2005)
• Van Slyke, Wets: L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming (SIAM, 1969)
• Rahmaniani, Crainic, Gendreau, Rei: The Benders Decomposition Algorithm – A Literature Review (CIRRELT-Arbeitspapier)
• Zuse-Institut Berlin, CO@Work 2020: Benders decomposition – Fundamentals (Vortragsfolien)
• Magnanti, Wong: Accelerating Benders Decomposition (Operations Research, 1981)
• Papadakos: Practical enhancements to the Magnanti–Wong method (Operations Research Letters, 2008)
• Laporte, Louveaux: The integer L-shaped method for stochastic integer programs with complete recourse (1993)
• Carøe, Schultz: Dual Decomposition in Stochastic Integer Programming (ZIB-Report)
• Fisher: The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Encyclopedia of Mathematics: Lagrangean relaxation
• Claude Lemaréchal: Ausgewählte Veröffentlichungen (Bündelverfahren)
• Zou, Ahmed, Sun: Stochastic Dual Dynamic Integer Programming (Optimization Online)
• Chen, Luedtke: On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs (arXiv)
• Füllner, Rebennack: Non-convex nested Benders decomposition (KIT-Bibliothek)
• Ntaimo, Sen: The million-variable „march“ for stochastic combinatorial optimization (edoc HU Berlin)
• SIPLIB: The SSLP Test Problems

Bücher zum Vertiefen

• John R. Birge, François Louveaux: Introduction to Stochastic Programming. 2. Auflage, Springer 2011.
• Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczyński: Lectures on Stochastic Programming. Modeling and Theory. SIAM, 2. Auflage 2014.
• Laurence A. Wolsey: Integer Programming. 2. Auflage, Wiley 2020.
• Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli: Integer Programming. Springer 2014.
• Dimitris Bertsimas, John N. Tsitsiklis: Introduction to Linear Optimization. Athena Scientific 1997.
• Wolfgang Domschke, Andreas Drexl, Robert Klein, Armin Scholl: Einführung in Operations Research. Springer Gabler, deutschsprachiges Lehrbuch in vielen Auflagen.