Ganzzahlige lineare Optimierung

Grundidee und mathematische Formulierung

Die ganzzahlige lineare Optimierung (englisch: integer linear programming, ILP) ist ein Teilgebiet der mathematischen Optimierung. Sie maximiert oder minimiert eine lineare Zielfunktion unter linearen Gleichungen und Ungleichungen. Der entscheidende Unterschied zur kontinuierlichen linearen Optimierung besteht darin, dass alle Variablen ganzzahlige Werte annehmen müssen. Sind nur einige Variablen ganzzahlig und andere kontinuierlich, handelt es sich um ein gemischt-ganzzahliges lineares Optimierungsproblem (MILP). Wegen der diskreten Variablen wird auch der Begriff diskrete Optimierung verwendet.

Ein ganzzahliges lineares Maximierungsproblem kann in der Form ILP: max {cᵀx | Ax ≤ b, x ≥ 0, x ∈ ℤⁿ} formuliert werden. Dabei ist A eine reelle Matrix, b und c sind Vektoren passender Dimension. Die Bedingung Ax ≤ b gilt komponentenweise: Für jede Zeile i von A gilt aᵢ · x = ∑ⱼ₌₁ⁿ aᵢⱼxⱼ ≤ bᵢ. Außerdem sind alle Einträge von x nichtnegativ. Es gibt mehrere äquivalente Formulierungen, die sich ineinander umwandeln lassen.

Die Ganzzahligkeitsbedingungen erweitern die Modellierungsmöglichkeiten erheblich. Variablen können beispielsweise Produktionsmengen darstellen, die nur als ganze Stückzahlen möglich sind. Besonders wichtig sind Binärvariablen, die nur die Werte 0 oder 1 annehmen und Entscheidungen ausdrücken, etwa ob eine Anlage gebaut, eine Linie bedient oder eine Zuordnung vorgenommen wird.

Geometrische Interpretation und typisches Beispiel

Lässt man in einem ILP die Ganzzahligkeitsbedingungen weg, entsteht die LP-Relaxierung. Die Menge P = {x ∈ ℝⁿ | Ax ≤ b, x ≥ 0} ist ein konvexes Polyeder im n-dimensionalen Raum. Seine begrenzenden Hyperebenen entsprechen den Zeilen des Ungleichungssystems. Das Polyeder enthält zwar alle zulässigen ganzzahligen Punkte, aber auch viele nichtganzzahlige Punkte, die im ursprünglichen Problem nicht zulässig sind.

Bei einem Maximierungsproblem ist der optimale Wert der LP-Relaxierung mindestens so groß wie der optimale Wert des ILP, weil die Relaxierung mehr Lösungen zulässt. Die eigentliche ganzzahlige zulässige Menge besteht nur aus den ganzzahligen Punkten innerhalb von P. Anders als bei linearen Programmen ist die Menge der Optimallösungen eines ILP keine Seitenfläche von P. Deshalb kann es genau eine, unendlich viele oder auch eine andere endliche Anzahl größer als 1 optimaler Lösungen geben. ILPs können unlösbar oder unbeschränkt sein. Bei rationalen Einträgen des Ungleichungssystems existiert in allen anderen Fällen mindestens eine Optimallösung. Bei nicht rationalen Daten kann trotz vorhandener Lösungen und beschränkter Zielfunktion eine Optimallösung fehlen.

Im Beispiel max y unter -x + y ≤ 1, 3x + 2y ≤ 12, 2x + 3y ≤ 12 sowie x,y ∈ ℤ≥0 sind (1;2) und (2;2) optimale ganzzahlige Lösungen mit Zielfunktionswert 2. Die LP-Relaxierung besitzt dagegen die eindeutige optimale Lösung LPopt = (1,8; 2,8) mit Wert 2,8; dieser Punkt ist nicht ganzzahlig.

Ein Beispiel ohne Optimallösung ist max {-√2x + y | -√2x + y ≤ 0, x ≥ 1, y ≥ 0, x,y ∈ ℤ}. Zulässige Lösungen wie (10;14) liefern rationale Approximationen y/x für √2. Da √2 irrational und beliebig genau approximierbar ist, bleibt die Zielfunktion nach oben beschränkt, ohne dass ein maximaler Wert angenommen wird.

Anwendungsfelder und 0/1-Programmierung

Ganzzahlige lineare Optimierung wird eingesetzt, wenn Stückzahlen ganzzahlig sein müssen oder wenn Entscheidungen durch Binärvariablen beschrieben werden. Wichtige Anwendungsfelder sind:

• Produktionsplanung: Für mehrere Produkte werden Produktionsmengen festgelegt, die gemeinsame Ressourcen wie Maschinen, Arbeitszeit oder Lagerkapazitäten nutzen. Ziel kann die Maximierung des gesamten Deckungsbeitrags sein, ohne die verfügbaren Ressourcen zu überschreiten.
• Öffentlicher Nahverkehr: Bei Dienst- und Umlaufplanung werden Busse oder U-Bahnen so auf Linien verteilt und Fahrern zugeordnet, dass der Fahrplan erfüllt wird. Binärvariablen geben etwa an, ob ein Bustyp eine Linie befährt oder ein Fahrer einem bestimmten Zug zugewiesen wird.
• Telekommunikationsnetze: Kapazitäten auf Knoten und Leitungen werden installiert und Kommunikationsbedarfe so geroutet, dass alle Bedarfe erfüllt werden und die Gesamtkosten minimal sind. Kapazitäten können meist nur in bestimmten ganzzahligen Einheiten installiert werden.
• Mobilfunknetze: Bei der Frequenzplanung in GSM-Netzen werden Frequenzen Antennen zugewiesen, sodass alle Nutzer bedient und Interferenzen minimiert werden. Binärvariablen beschreiben, ob eine Frequenz einer bestimmten Antenne zugeteilt ist.
• Tourenplanung: Beim Problem des Handlungsreisenden wird eine kürzeste Rundreise durch eine gegebene Menge von Städten gesucht. Das Modell enthält exponentiell viele Ungleichungen. Varianten treten beim Bohren von Leiterplatten und bei Fahrtrouten von Außendienstmitarbeitern auf. Eine Verallgemeinerung ist das Vehicle Routing Problem zur Planung optimaler Touren für Fahrzeugflotten oder Gruppen von Reisenden.

Bei der 0/1-Programmierung sind alle Variablen auf 0 oder 1 beschränkt. Dadurch kann die Suche nach Lösungen Boolescher Funktionen geometrisch als Suche nach 0/1-Punkten in Schnitt und Vereinigung hochdimensionaler Polytope dargestellt werden. Diese Methode heißt disjunktive Programmierung und wurde Ende der 1960er Jahre von Egon Balas entwickelt. 0/1-Programmierung ist kombinatorisch schwierig und gehört zu Karps 21 NP-vollständigen Problemen.

Komplexität sowie exakte und heuristische Verfahren

Das Finden einer beweisbaren Optimallösung für ganzzahlige Programme ist NP-schwer. Lineare Programme können beispielsweise mit Innere-Punkte-Verfahren in Polynomialzeit optimal gelöst werden; bei ILPs hängt die praktische Lösbarkeit dagegen stark von Problemstruktur und Modellierung ab. Ein Problem mit hundert ganzzahligen Variablen kann praktisch unlösbar sein, während ein anderes mit tausenden Variablen innerhalb weniger Sekunden lösbar ist. Deshalb werden häufig mehrere Verfahren kombiniert und problemspezifisch angepasst.

Exakte Verfahren finden bei beliebig langer Laufzeit stets eine beweisbare Optimallösung oder stellen fest, dass das Problem unlösbar oder unbeschränkt ist. Dazu gehören Branch-and-Bound, Schnittebenenverfahren und die Kombination Branch-and-Cut. Eine besondere Erleichterung entsteht, wenn das Polyeder bereits nur ganzzahlige Extremalpunkte besitzt, etwa bei total unimodularen Matrizen. Dann kann das Problem beispielsweise direkt mit dem Simplex-Algorithmus gelöst werden. Auch Lift-and-Project verfolgt die Idee, durch eine Beschreibung in einem höherdimensionalen Raum und anschließende Projektion eine geeignete ganzzahlige Struktur zu erhalten.

Heuristiken liefern meist schnell zulässige Lösungen, geben aber normalerweise keine Garantie über deren Abstand zur Optimallösung. Findet eine Heuristik keine Lösung, bleibt offen, ob der Algorithmus versagt oder das Problem unlösbar ist. Problemspezifische Verfahren sind etwa Minimum-Spanning-Tree- und k-Opt-Heuristiken für das Problem des Handlungsreisenden. Metaheuristiken umfassen unter anderem Runden von LP-Lösungen, lokale Suche, Tabu-Suche, evolutionäre Algorithmen, Simulated Annealing, Variable Nachbarschaftssuche und Ameisenalgorithmen. Ihre einzelnen Schritte müssen an das jeweilige Problem angepasst werden. Als alleinige Verfahren sind sie begrenzt, können aber in Branch-and-Cut zur schnellen Erzeugung guter zulässiger Lösungen eingesetzt werden.

Schranken, Schnitte und Verzweigung

Exakte Verfahren lösen wiederholt Relaxierungen, also einfachere Probleme, deren Lösungsmenge alle Lösungen des ursprünglichen Problems enthält. Die LP-Relaxierung liefert bei Maximierung eine obere beziehungsweise duale Schranke. Der Wert jeder bekannten zulässigen ganzzahligen Lösung ist eine untere beziehungsweise primale Schranke. Aus der Differenz ergibt sich der absolute Optimalitätsgap. Der relative Gap wird typischerweise durch Division durch die untere Schranke berechnet.

Im Beispiel beträgt der LP-Wert 2,8. Eine zulässige Lösung (1;1) hat den Wert 1. Der absolute Gap ist daher 2,8 − 1 = 1,8, der relative Gap 1,8/1 = 1,8 = 180 %. Der tatsächliche Unterschied zum optimalen ganzzahligen Wert 2 beträgt dagegen 100 %. Während des Lösungsverfahrens wird die Relaxierung verschärft, sodass die obere Schranke sinkt, und es werden bessere zulässige Lösungen gesucht, sodass die untere Schranke steigt. Stimmen beide Schranken überein, ist die gefundene Lösung nachgewiesen optimal.

Schnittebenenverfahren lösen zunächst die LP-Relaxierung und fügen anschließend Ungleichungen hinzu, die alle zulässigen ganzzahligen Punkte erfüllen, die aktuelle gebrochene LP-Lösung aber nicht. Im Beispiel trennt x + 2y ≤ 6 das bisherige LP-Optimum ab. Die neue LP-Lösung (4/3; 7/3) hat den Wert 7/3; der relative Gap zur Lösung (1;1) sinkt dadurch auf (7/3 − 1)/1 = 4/3 ≈ 133 %. Besonders gute Schnittebenen sind Facetten des IP-Polyeders, im Beispiel y ≤ 2 und x + y ≤ 4. Allein können Schnittebenen numerische Probleme verursachen oder nicht ausreichen.

Branch-and-Bound zerlegt eine gebrochene LP-Lösung in Teilprobleme, sodass jede zulässige Lösung in einem Teilproblem enthalten ist. Im Beispiel wird aus (1,8;2,8) in x ≤ 1 und x ≥ 2 verzweigt. Die Relaxierung des rechten Teilproblems liefert (2;8/3) mit Wert 8/3, die des linken die ganzzahlige Lösung (1;2) mit Wert 2. Damit liegen die Schranken bei 2 und 8/3; der relative Gap beträgt (8/3 − 2)/2 = 1/3. Weil (1;2) eine ganzzahlige Lösung einer Relaxierung des ursprünglichen Problems ist, ist sie bereits optimal. Teilbäume können abgeschnitten werden, wenn ihre duale Schranke keine bessere Lösung zulässt. Branch-and-Cut verbindet diese Verzweigung mit Schnittebenen und wird von leistungsfähigen ILP-Lösern häufig eingesetzt.

Historische Entwicklung

Die Entwicklung der ganzzahligen Optimierung ist eng mit der linearen Optimierung verbunden. 1947 veröffentlichte George Dantzig wichtige Arbeiten zur linearen Optimierung und zum Simplex-Verfahren und entwickelte diese später mit John von Neumann und anderen weiter. Mit den ersten praktisch einsetzbaren Computerprogrammen in den 1950er Jahren wurde auch die Lösung ganzzahliger Probleme realistisch.

D. R. Fulkerson, G. Dantzig und S. Johnson untersuchten Mitte der 1950er Jahre erste Schnittebenen für das Problem des Handlungsreisenden. Ralph Gomory entwickelte 1958 in Princeton das erste allgemein einsetzbare Schnittebenenverfahren. 1960 stellten Ailsa Land und Alison Doig das Branch-and-Bound-Verfahren vor; 1965 beschrieb R. J. Dakin dazu einen einfach implementierbaren Algorithmus. Später kombinierte Egon Balas Branch-and-Bound mit Schnittebenen zu Branch-and-Cut.

Ende der 1960er Jahre entstand unter anderem Balas’ Methode Lift-and-Project. In den 1980er Jahren entwickelten Manfred Padberg und andere Schnittebenen für häufige Teilstrukturen wie Rucksackprobleme. Fortschritte bei linearen Optimierungsverfahren in den 1990er Jahren verbesserten auch die ganzzahlige Optimierung, weil bei Branch-and-Bound und Schnittebenenverfahren zahlreiche lineare Programme gelöst werden müssen. Parallel wurden zahlreiche Heuristiken entwickelt. Die Weiterentwicklung exakter Verfahren, Modellierungen und Heuristiken ist weiterhin Gegenstand der Forschung.