Mathematische Formulierung

Ein ganzzahliges Programm (englisch integer program, IP) hat die gleiche Form wie ein lineares Programm (LP), mit dem Unterschied, dass die Variablen ganzzahlig sein müssen:

${\displaystyle \max _{x\in \mathbb {Z} ^{n}}\left\{c^{T}x\;|\;Ax\leq b,x\geq 0\right\}}$

Dabei ist ${\displaystyle A}$ eine reelle Matrix und ${\displaystyle b}$ und ${\displaystyle c}$ sind Vektoren passender Dimension. Die Bedingung ${\displaystyle Ax\leq b}$ ist komponentenweise zu verstehen, also als

${\displaystyle a_{i}\cdot x=\sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}}$

für alle Zeilen ${\displaystyle i}$ der Matrix ${\displaystyle A}$. Genauso bedeutet die Bedingung ${\displaystyle x\geq 0}$, dass alle Einträge des Vektors ${\displaystyle x}$ nichtnegativ sein müssen. Gelten die Ganzzahligkeitsbedingungen nur für einen Teil der Variablen, spricht man auch von einem gemischt-ganzzahligen Programm (engl. mixed-integer program, MIP). Auch die Präzisierung ganzzahliges lineares Programm (engl. integer linear program, ILP) ist gebräuchlich. Wie auch in der linearen Optimierung gibt es mehrere äquivalente Formulierungen, die sich ineinander transformieren lassen (siehe Lineare Optimierung: Problemdefinition).

Geometrische Interpretation

Die ganzzahlige Optimierung lässt sich, wie die lineare Variante, zu einem großen Teil geometrisch interpretieren. Die Menge

${\displaystyle P:=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b,x\geq 0\},}$

die durch Weglassen der Ganzzahligkeitsbedingungen entsteht, bildet ein konvexes Polyeder im ${\displaystyle n}$-dimensionalen Raum, dessen beschränkende Hyperebenen den Zeilen des Ungleichungssystems entsprechen. ${\displaystyle P}$ enthält u. a. alle zulässigen Punkte des Ausgangssystems, also alle ganzzahligen Punkte, die die Bedingungen ${\displaystyle Ax\leq b}$ erfüllen, aber im Unterschied zur linearen Optimierung sind nicht alle Punkte in ${\displaystyle P}$ zulässig. Das lineare Programm

${\displaystyle \max \,\{c^{T}x\;|\;x\in P\}}$

wird als LP-Relaxierung des ganzzahligen Problems bezeichnet und spielt eine bedeutende Rolle für einige Lösungsverfahren (siehe unten).

Wie lineare Programme können auch ganzzahlige Programme unlösbar oder unbeschränkt sein. In allen anderen Fällen gibt es mindestens eine Optimallösung, sofern das Ungleichssystem nur rationale Einträge hat. Es ist im Gegensatz zur reellen linearen Optimierung möglich, Probleme zu konstruieren, die keine Optimallösung haben, obwohl Lösungen existieren und die Zielfunktion beschränkt ist. Im Unterschied zu LPs ist die Menge der Optimallösungen eines IPs keine Seitenfläche des Polyeders ${\displaystyle P}$, so dass es neben genau einer oder unendlich vielen optimalen Lösungen auch eine andere endliche Anzahl (größer als 1) davon geben kann.

Produktionsplanung

In der Produktionsplanung taucht oft das Problem auf, Produktionsmengen für mehrere Produkte zu bestimmen, die sich gemeinsame Ressourcen (Maschinen, Arbeitszeit, Lagerkapazitäten …) teilen. Ziel ist beispielsweise die Maximierung des gesamten Deckungsbeitrags, ohne die vorhandenen Ressourcen zu überschreiten. In einigen Fällen lässt sich dies mit Hilfe eines linearen Programms ausdrücken, aber oft müssen die Variablen aus praktischen Gründen ganzzahlig sein (s. o.).

Öffentlicher Nahverkehr

Bei der Dienst- und Umlaufplanung im öffentlichen Nahverkehr geht es darum, beispielsweise Busse oder U-Bahnen so auf die einzelnen Linien zu verteilen, dass der Fahrplan erfüllt werden kann, und sie mit Fahrern auszustatten. Hier spielen binäre Entscheidungsvariablen eine große Rolle, die z. B. ausdrücken, ob ein bestimmter Bustyp eine Linie befährt oder nicht, oder ob ein U-Bahn-Fahrer einem bestimmten Zug zugewiesen wird oder nicht.

Telekommunikationsnetze

Ziel der Kapazitäts- und Routing-Planung in landesweiten Telekommunikationsnetzen ist es, Kapazität auf den Knoten und Leitungen eines Netzes so zu installieren und Kommunikationsbedarfe darin so zu routen, dass alle Bedarfe erfüllt werden und die Gesamtkosten des Netzes minimal sind. Die Kapazität kann in der Regel nicht in beliebigen Anteilen installiert werden, sondern nur in bestimmten ganzzahligen Einheiten. Meist gibt es, abhängig von der verwendeten Technologie, noch weitere Beschränkungen, die sich als lineare Ungleichungen mit ganzzahligen oder binären Variablen modellieren lassen.

Mobilfunknetze

Die Aufgabe der Frequenzplanung in GSM-Mobilfunknetzen besteht darin, die verfügbaren Frequenzen so auf die Antennen zu verteilen, dass alle Nutzer bedient werden können und die störende Interferenz zwischen den Antennen minimiert wird. Dieses Problem lässt sich als ganzzahliges lineares Programm formulieren, bei dem u. a. Binärvariablen repräsentieren, ob eine Frequenz einer bestimmten Antenne zugewiesen wird oder nicht.

Tourenplanung

Die Tourenplanung, speziell das Problem des Handlungsreisenden, ist ein klassisches Beispiel der ganzzahligen Optimierung, dessen Untersuchung viel zur Entwicklung allgemeiner Lösungsverfahren beigetragen hat. Anschaulich geht es darum, eine kürzeste Rundreise zwischen einer gegebenen Menge von Städten zu finden. Dieses Problem kann als ganzzahliges lineares Programm mit exponentiell vielen Ungleichungen modelliert werden. Verschiedene erweiterte Varianten der Tourenplanung tauchen in der Praxis beispielsweise beim Bohren von Leiterplatten auf, oder auch bei der Planung der Fahrtrouten für Außendienstmitarbeiter (z. B. eines technischen Kundendienstes oder einer Versicherung), die alle ihre Kunden mit möglichst kurzen Wegen bedienen wollen.

0/1-Programmierung

Ein besonders wichtiger Spezialfall der ganzzahligen Optimierung ist die Optimierung, bei der die Variablen nicht nur ganzzahlige Werte annehmen dürfen, sondern auf die binären Werte 0 oder 1 beschränkt sind. Dadurch lässt sich die Suche nach Lösungen für Boolesche Funktionen in die Geometrie übertragen: Das Finden einer Belegung einer solchen Funktion wird äquivalent zum Finden von 0/1-Punkten in Schnitt und der Vereinigung von hochdimensionalen Polytopen. Diese Methode wird disjunktive Programmierung genannt und wurde Ende der 1960er Jahre von Egon Balas entwickelt. 0/1-Programmierung ist ein kombinatorisch schwieriges Problem und gehört zu Karps 21 NP-vollständigen Problemen.

Exakte und heuristische Verfahren

Bei der Klassifizierung der Algorithmen ist zu unterscheiden zwischen exakten und heuristischen Lösungsverfahren.

Heuristische Verfahren liefern typischerweise zulässige Lösungen in relativ kurzer Zeit, aber keine Information darüber, wie gut diese im Vergleich zu einer Optimallösung sind. Wenn eine Heuristik keine Lösung findet, ist nicht bekannt, ob dies am Algorithmus liegt oder ob das betrachtete Optimierungsproblem prinzipiell unlösbar ist. Heuristische Verfahren sind meist an das zu lösende Problem angepasst, wie beispielsweise die k-Opt-Heuristiken für das Problem des Handlungsreisenden. Bei Metaheuristiken wie Tabu-Suche ist zwar der grundsätzliche Ablauf generisch, aber die einzelnen Schritte des Algorithmus müssen abhängig vom betrachteten Problem definiert werden.

Exakte Verfahren finden beweisbar stets eine optimale Lösung oder stellen fest, dass das Problem unlösbar oder unbeschränkt ist, vorausgesetzt, man lässt den Algorithmus beliebig lange laufen. Beispiele hierfür sind Branch-and-Bound, Schnittebenenverfahren sowie deren Kombination Branch-and-Cut. In der Praxis kann man diese Verfahren durch Anpassung an das zu lösende Problem und durch Kombination mit Heuristiken oft deutlich beschleunigen. Ein eleganter Weg, schnell eine exakte Lösung zu finden, besteht darin, den Suchraum – das konvexe Polyeder im n-dimensionalen Raum, das alle möglichen Lösungen enthält – von vornherein so zu modellieren, dass er nur ganzzahlige Extremalpunkte enthält. Dies ist beispielsweise für total unimodulare Matrizen der Fall. Das Polyeder wird also nicht nachträglich mit Schnittebenen verkleinert. Gelingt das – zum Beispiel durch Lift-and-Project –, dann kann man die Optimierungsaufgabe einfach zum Beispiel durch Ausführen des Simplex-Algorithmus lösen.

Duale Schranken und Optimalitätsbeweis

Alle praktisch relevanten exakten Verfahren beruhen auf der iterativen Lösung und Modifikation einer Relaxierung, also eines einfacheren Problems, dessen Lösungsmenge alle Lösungen des Ursprungsproblems enthält. Beispielsweise verwenden Branch-and-Bound und Schnittebenenverfahren die LP-Relaxierung, lassen also zunächst die Ganzzahligkeitsbedingungen weg. Dies lässt sich auch geometrisch interpretieren: Eigentlich ist eine optimale Ecke des IP-Polyeders ${\displaystyle P_{I}}$ (im obigen Bild rot gestrichelt) gesucht, das von allen zulässigen ganzzahligen Punkten aufgespannt wird. Da dieses Polyeder meist nicht genau bekannt ist, wird stattdessen eine optimale Ecke des Polyeders ${\displaystyle P}$ der LP-Relaxierung gesucht, das ${\displaystyle P_{I}}$ enthält (im obigen Beispiel blau umrandet). Dies geht verhältnismäßig einfach, z. B. mit dem Simplex-Verfahren.

Da in der Relaxierung mehr Lösungen zugelassen sind als im Ausgangsproblem, ist ihr Optimalwert mindestens so hoch (bei einem Maximierungsproblem) wie der – unbekannte – Optimalwert des IPs, liefert also für diesen eine obere (allgemein: duale) Schranke. Gleichzeitig definiert der Wert jeder zulässigen ganzzahligen Lösung ${\displaystyle L}$ eine untere (allgemein: primale) Schranke für den Wert einer Optimallösung, da diese ja per Definition mindestens so gut ist wie ${\displaystyle L}$. Durch Vergleich der oberen und unteren Schranken kann ein maximaler relativer Abstand, der sogenannte Optimalitätsgap, zwischen dem Wert einer gefundenen Lösung und dem Optimalwert angegeben werden, ohne diesen genau zu kennen.

Im obigen Beispiel beträgt der optimale Wert der LP-Relaxierung 2,8. Der Optimalwert des ganzzahligen Problems kann nicht höher sein, da dort weniger Lösungen zugelassen sind als in der LP-Relaxierung. Der Punkt ${\displaystyle (1;1)}$, den man beispielsweise durch Raten oder über eine Heuristik gefunden haben kann, ist eine zulässige Lösung des ganzzahligen Problems und hat den Zielfunktionswert 1. Eine optimale Lösung ist per Definition mindestens genauso gut wie die gefundene Lösung. Der Optimalwert des ganzzahligen Problems muss also zwischen 1 und 2,8 liegen. Der absolute Optimalitätsgap ist die Differenz zwischen der oberen und unteren Schranke, hier also ${\displaystyle (2{,}8-1)=1{,}8.}$ Der häufiger angegebene relative Optimalitätsgap ergibt sich durch Normierung dieses Wertes mit der unteren Schranke, in diesem Fall also als ${\displaystyle 1{,}8/1=1{,}8=180\,\%.}$ Er besagt, dass der Optimalwert des ganzzahligen Programms um höchstens 180 % höher liegt als der Wert der Lösung ${\displaystyle (1;1)}$. Dies erlaubt eine (in diesem Fall nicht besonders gute) Qualitätsabschätzung der Lösung. Der tatsächliche Unterschied beträgt ${\displaystyle (2-1)/1=1=100\,\%}$, d. h. der Optimalwert ist doppelt so hoch wie der Wert der gefundenen Lösung.

Im Laufe des Algorithmus wird die Relaxierung schrittweise verschärft (beispielsweise durch Hinzufügen zusätzlicher Ungleichungen), so dass die sich daraus ergebende obere Schranke immer kleiner wird. Gleichzeitig wird versucht, bessere zulässige Lösungen zu finden, um die untere Schranke anzuheben. Dies ist in der nebenstehenden Abbildung illustriert. Sind der Wert einer gefundenen Lösung und die duale Schranke gleich (im Beispiel beim Wert 2), ist dies der Beweis, dass die gefundene Lösung optimal ist.

Im Folgenden werden einige wichtige exakte und heuristische Lösungsverfahren etwas genauer vorgestellt.

Schnittebenenverfahren

Schnittebenenverfahren (englisch cutting plane algorithm) berechnen zunächst eine Lösung der LP-Relaxierung. Diese ist meist nicht ganzzahlig, liefert aber eine duale Schranke für den Optimalwert des IPs. Diese duale Schranke wird anschließend durch schrittweises Hinzufügen sogenannter Schnittebenen verschärft. Eine Schnittebene ist eine zusätzliche Ungleichung, die von allen zulässigen Punkten des IPs erfüllt wird, aber nicht von der aktuellen LP-Lösung. Wird die Ungleichung dem LP hinzugefügt, muss daher beim erneuten Lösen eine andere Lösung herauskommen. Dies wird solange fortgeführt, bis eine ganzzahlige Lösung gefunden wird (die dann automatisch auch optimal für das ganzzahlige Programm ist) oder keine geeigneten Ungleichungen mehr gefunden werden.

Geometrisch entspricht dieses Vorgehen dem Hinzufügen einer Hyperebene, welche die optimale Ecke des LP-Polyeders ${\displaystyle P}$ von dem (unbekannten) Polyeder abschneidet, das von den ganzzahligen Lösungen aufgespannt wird. Beim erneuten Lösen wird eine optimale Ecke des beschnittenen Polyeders bestimmt. Ist diese ganzzahlig, so hat man eine zulässige und optimale Lösung des ganzzahligen linearen Programms gefunden. Andernfalls wird wieder nach einer neuen Schnittebene gesucht.

Im nebenstehenden Bild ist die Schnittebene ${\displaystyle x+2y\leq 6}$ (grün) dargestellt, die das bisherige LP-Optimum (blau) vom IP-Polyeder trennt (separiert). Alle zulässigen Punkte liegen auf einer Seite der Hyperebene, die LP-Lösung auf der anderen Seite. Erneutes Lösen des LPs mit dieser zusätzlichen Ungleichung liefert den grün markierten Punkt (4/3;7/3). Dieser Punkt ist immer noch nicht zulässig, hat aber den kleineren Zielfunktionswert 7/3, wodurch sich beispielsweise der relative Optimalitätsgap für die Lösung (1;1) von 180 % auf ${\displaystyle (7/3-1)/1=4/3\approx 133\,\%}$ verringert.

In der praktischen Anwendung sind Schnittebenenverfahren ein wichtiges Hilfsmittel, reichen aber allein meist nicht aus und können bei unvorsichtiger Anwendung zu numerischen Problemen führen. Stattdessen werden sie häufig mit Branch-and-Bound kombiniert. Wie gut das funktioniert, hängt stark von der Struktur des zu lösenden Problems ab. Die besten Schnittebenen, die man finden kann, sind Facetten des IP-Polyeders. Im obigen Beispiel sind das die Ungleichungen ${\displaystyle y\leq 2}$ und ${\displaystyle x+y\leq 4}$, die den rot gestrichelten Linien entsprechen. Um solche Ungleichungen zu identifizieren, ist meist eine genauere mathematische Untersuchung der zugrundeliegenden Polyeder notwendig.

Branch-and-Bound bzw. Branch-and-Cut

Auch Branch-and-Bound beginnt mit dem Lösen der LP-Relaxierung. Ist die erhaltene Lösung nicht ganzzahlig, wird das Problem so in zwei oder mehr Teilprobleme zerlegt, dass jede zulässige Lösung in einem dieser Teilprobleme enthalten ist. Auf diese Art wird ein Verzweigungsbaum mit der LP-Relaxierung als Wurzelknoten aufgebaut. An jeder Verzweigung (englisch branch) wird der Wertebereich einer oder mehrerer Variablen eingeschränkt. Dies wird solange durchgeführt, bis eine beste ganzzahlige Lösung gefunden wurde.

In dieser reinen Form entspricht das Verfahren einer vollständigen Enumeration aller möglichen Lösungen. Mit Hilfe der dualen Schranken, die man durch die Lösung der Relaxierungen an jedem Knoten des Verzweigungsbaums erhält, können aber Teilbäume abgeschnitten werden (engl. bound), wenn sich erweist, dass sie keine Optimallösung enthalten können. Als alleiniger Algorithmus reicht Branch-and-Bound meist nicht aus, weil zu wenig vom Suchbaum abgeschnitten werden kann. Gute IP-Löser kombinieren dieses Verfahren daher zur Verbesserung der dualen Schranke mit Schnittebenenverfahren. Dieser Ansatz heißt dann Branch-and-Cut.

Im nebenstehenden Beispiel werden, ausgehend von der gebrochenen LP-Lösung ${\displaystyle (1{,}8;2{,}8)}$, die beiden Teilprobleme betrachtet, die durch Hinzufügen der zusätzlichen Bedingung ${\displaystyle x\leq 1}$ bzw. ${\displaystyle x\geq 2}$ entstehen. Jede zulässige Lösung ist in genau einem der beiden Teilpolyeder (grün umrandet) enthalten. Das Lösen der LP-Relaxierung mit den zusätzlichen Bedingungen liefert im rechten Teilproblem die gebrochene Lösung ${\displaystyle (2;8/3)}$ mit dem Zielfunktionswert ${\displaystyle 8/3}$ und im linken Teilproblem die ganzzahlige Lösung ${\displaystyle (1;2)}$ mit dem Wert 2. Dadurch verbessert sich die untere Schranke für den optimalen IP-Wert auf 2 (der Wert der besten bekannten zulässigen Lösung), während sich die obere Schranke auf ${\displaystyle 8/3}$ verringert (der höhere LP-Wert der beiden Teilprobleme). Der Optimalitätsgap reduziert sich damit auf ${\displaystyle (8/3-2)/2=1/3}$, d. h. der Optimalwert ist höchstens ${\displaystyle (1+1/3)}$ mal so hoch wie der Wert der Lösung ${\displaystyle (1;2)}$. Tatsächlich ist diese Lösung bereits optimal, da sie eine ganzzahlige Lösung einer Relaxierung des ursprünglichen Problems ist.

Lagrange-Relaxierung

Die Lagrange-Relaxierung ist ein Verfahren aus der nichtlinearen Optimierung, das auch auf die ganzzahlige Optimierung angewandt werden kann. Die Grundidee besteht darin, „störende“ Ungleichungen wegzulassen, so dass das verbleibende Problem (mit Ganzzahligkeitsbedingungen) leicht lösbar ist, und stattdessen die Verletzung dieser Ungleichungen, gewichtet mit sogenannten Lagrange-Multiplikatoren, in der Zielfunktion zu bestrafen.

Eine Lösung dieses einfacheren Problems wird in den meisten Fällen die in die Zielfunktion relaxierten Bedingungen nicht erfüllen. Um dies zu ändern, werden die Lagrange-Multiplikatoren mit Hilfe eines Subgradientenverfahrens abhängig von der aktuellen (unzulässigen) Lösung so angepasst, dass ein erneutes Lösen mit den neuen Gewichten eine etwas „zulässigere“ Lösung erzeugt, welche die relaxierten Ungleichungen weniger stark verletzt. Dieser Prozess wird iterativ wiederholt, bis alle Bedingungen erfüllt sind. Man kann zeigen, dass jede Lösung einer Lagrange-Relaxierung eine duale Schranke für das ursprüngliche IP liefert, und dass dieses Verfahren bei geeigneter Anpassung der Multiplikatoren konvergiert.

Heuristiken

Für fast jedes Optimierungsproblem lassen sich leicht eine Vielzahl von Heuristiken finden, die für dieses spezielle Problem schnell zulässige Lösungen finden. Dagegen ist die Entwicklung heuristischer Verfahren, die zuverlässig gute Lösungen finden, und das möglichst auch noch für eine ganze Klasse verwandter Optimierungsprobleme und nicht nur für ein spezielles Problem, eine nicht triviale Aufgabe.

Beispiele für problemspezifische Heuristiken beim Problem des Handlungsreisenden sind die Minimum-Spanning-Tree-Heuristik zur Konstruktion einer zulässigen Tour mit Hilfe eines minimal aufspannenden Baumes und die k-Opt-Heuristiken zur Verbesserung einer bereits gefundenen Tour. Dieses Optimierungsproblem ist auch eines der wenigen Beispiele, bei denen sich leicht heuristische duale Schranken angeben lassen. Beispielsweise enthält jede Tour durch ${\displaystyle n}$ Knoten auch genau ${\displaystyle n}$ Kanten, so dass eine kürzeste Tour mindestens so lang sein muss wie die Summe der ${\displaystyle n}$ kürzesten Kantenlängen. Im Allgemeinen ist es deutlich schwieriger, gute duale Schranken anzugeben.

Neben solchen speziell für ein Problem entwickelten Verfahren gibt es sogenannte Metaheuristiken, die auf problemunabhängige Weise Strategien zur Suche zulässiger Lösungen beschreiben. Die einzelnen Schritte dieser Algorithmen müssen allerdings speziell auf das zu lösende Problem angepasst werden. Beispiele hierfür sind das Runden von LP-Lösungen, lokale Suche, Tabu-Suche, Evolutionäre Algorithmen, Simulated Annealing, Variable Nachbarschaftssuche und Ameisenalgorithmen. Einige dieser Verfahren haben Prozesse wie die natürliche Selektion oder das Verhalten von Ameisen auf der Suche nach Futter zum Vorbild; inwieweit das für die Lösungsqualität und die Lösungszeiten in der Praxis von Vorteil ist, ist umstritten.

Als alleiniges Lösungsverfahren haben all diese Algorithmen den Nachteil, dass sie erstens nicht immer eine Lösung finden, und zweitens meistens nichts über die Qualität gefundener Lösungen im Vergleich zu einer Optimallösung bekannt ist. Sie können aber beispielsweise sehr sinnvoll im Rahmen eines Branch and Cut-Ansatzes eingesetzt werden, um an verschiedenen Knoten des Suchbaumes beispielsweise aus der aktuellen LP-Lösung gute zulässige Lösungen zu generieren und so evtl. Teile des Baumes abschneiden zu können.