Die ganzzahlige lineare Optimierung (manchmal kurz auch ganzzahlige Optimierung, engl.: integer linear programming (ILP)) ist ein Teilgebiet der mathematischen Optimierung. Wie die (kontinuierliche) lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung alle Variablen nur ganzzahlige Werte annehmen dürfen. Falls nur einige der Entscheidungsvariablen ganzzahlig und andere kontinuierlich sind, so spricht man von einem gemischt-ganzahligen Optimierungsproblem. Im Unterschied zur linearen Optimierung lassen sich mit Hilfe der ganzzahligen linearen Optimierung Optimierungsprobleme modellieren, die aus komplexitätstheoretischer Sicht NP-schwer sind.

Da die Variablen diskret, also nicht kontinuierlich sind, ist auch der Begriff diskrete Optimierung gebräuchlich. Eine weitere häufige Bezeichnung ist ganzzahlige (lineare) Programmierung (von engl. ), wobei der Begriff Programm im Sinne von Planung zu verstehen ist und nicht im Sinne eines Computerprogramms. Er wurde schon in den 1940er Jahren von George Dantzig geprägt, bevor Computer zur Lösung von Optimierungsproblemen eingesetzt wurden.

Noch stärker als die kontinuierliche lineare hat sich die ganzzahlige lineare Optimierung seit ihren Anfängen in den 1950er Jahren zu einem Modellierungs- und Optimierungswerkzeug für viele praktische Probleme entwickelt, für die keine speziellen Algorithmen bekannt sind. Durch bedeutende Fortschritte in der Entwicklung der Lösungsverfahren in den 1980er und 1990er Jahren hat die ganzzahlige Optimierung heute viele Anwendungen, beispielsweise in der Produktion, in der Planung von Telekommunikations- und Nahverkehrsnetzen und in der Tourenplanung.

Zur Lösung ganzzahliger Optimierungsprobleme gibt es einerseits exakte Lösungsverfahren wie beispielsweise Branch-and-Bound und Schnittebenenverfahren und andererseits eine Vielzahl von Heuristiken. Trotzdem ist die Lösung ganzzahliger linearer Programme in der Praxis immer noch eine schwere Aufgabe, die je nach Größe und Struktur des zu lösenden Problems eine geschickte Modellierung und mehr oder weniger speziell entwickelte oder angepasste Algorithmen erfordert. Oft werden daher mehrere Lösungsverfahren kombiniert.

Problemdefinition

Mathematische Formulierung

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

Dabei ist eine reelle Matrix und und sind Vektoren passender Dimension. Die Bedingung ist komponentenweise zu verstehen, also als

für alle Zeilen der Matrix . Genauso bedeutet die Bedingung , dass alle Einträge des Vektors nichtnegativ sein müssen. Gelten die Ganzzahligkeitsbedingungen nur für einen Teil der Variablen, spricht man auch von einem gemischt-ganzzahligen linearen Optimierungsproblem (engl. , MILP). 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

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

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 Ungleichungssystem 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 ILPs keine Seitenfläche des Polyeders , so dass es neben genau einer oder unendlich vielen optimalen Lösungen auch eine andere endliche Anzahl (größer als 1) davon geben kann.

Beispiele

mini|Polytop der zulässigen ganzzahligen Punkte (rot) mit LP-Relaxierung (blau) Im nebenstehenden Bild ist das ganzzahlige lineare Programm

dargestellt. Die zulässigen ganzzahligen Punkte sind rot eingezeichnet, und die rot gestrichelten Linien kennzeichnen ihre konvexe Hülle, also das kleinste Polyeder, das alle diese Punkte enthält. Über diesem Polyeder soll eigentlich optimiert werden, aber es ist meist nicht genau bekannt. Die blauen Linien zusammen mit den Koordinatenachsen begrenzen das Polyeder der LP-Relaxierung, das durch das Ungleichungssystem ohne Ganzzahligkeitsbedingungen gegeben ist. Ziel der Optimierung ist es, die schwarz gestrichelte Linie so weit parallel nach oben (in Richtung des Vektors ) zu verschieben, dass sie das jeweilige Polyeder gerade noch berührt. Die Optimallösungen des ganzzahligen Problems sind also die Punkte und mit dem Zielfunktionswert . Die – in diesem Fall eindeutige – optimale Lösung der LP-Relaxierung mit dem Zielfunktionswert 2,8 ist der blau markierte Punkt , der nicht ganzzahlig und damit auch nicht zulässig für das IP ist.

Das folgende IP ist ein Beispiel für den oben erwähnten Spezialfall:

Die zulässigen Lösungen wie z. B. stellen rationale Approximationen für in der Form dar. Da irrational ist und daher beliebig genau approximiert werden kann, gibt es keine Optimallösung, obwohl die Zielfunktion durch die erste Bedingung nach oben beschränkt ist.

Anwendungen

Die Ganzzahligkeitsbedingungen erweitern die Modellierungsmöglichkeiten für praktische Probleme gegenüber der linearen Optimierung beträchtlich. Es gibt zwei Hauptgründe für ganzzahlige Variablen: Die Variablen müssen aus praktischen Gründen ganzzahlig sein. Beispielsweise können nicht 3,7 Flugzeuge gebaut werden, sondern nur eine ganze Anzahl. Die ganzzahligen Variablen sind auf die Werte 0 oder 1 beschränkt (sogenannte Binärvariablen) und repräsentieren Entscheidungen. Beispielsweise kann ein Bus nicht zu einem Drittel fahren, sondern nur entweder ganz oder gar nicht. Oft treten auch beide Fälle zusammen auf. Die ganzzahlige Optimierung kann in vielen praktischen Anwendungsfeldern eingesetzt werden, von denen nachfolgend einige kurz beschrieben werden sollen.

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. Eine Verallgemeinerung stellt das Vehicle Routing Problem (auch Standardproblem der Tourenplanung) dar, in welchem optimale Touren für Fahrzeugflotten bzw. für Gruppen von Reisenden bestimmt werden sollen.

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.

Geschichte

Der Beginn der ganzzahligen Optimierung hängt eng mit der Entwicklung der linearen Optimierung Mitte der 1940er Jahre zusammen. Im Jahre 1947 veröffentlichte George Dantzig mehrere entscheidende Arbeiten zur linearen Optimierung und zum Simplex-Verfahren, die er in den darauffolgenden Jahren zusammen mit John von Neumann und anderen weiterentwickelte.

Als mit dem Aufkommen von Computern in den 1950er Jahren die ersten praktisch einsetzbaren Computerprogramme zur Lösung linearer Programme entwickelt wurden, rückte auch die Lösbarkeit ganzzahliger Optimierungsprobleme in erreichbare Nähe. Mitte der 1950er Jahre arbeiteten D. R. Fulkerson, G. Dantzig, und S. Johnson an ersten Schnittebenen für das Problem des Handlungsreisenden. Ohne Kenntnis dieser Arbeiten und motiviert durch ehemalige Kollegen der US Navy, die an ganzzahligen Lösungen interessiert waren, entwickelte Ralph Gomory im Jahre 1958 während seines Aufenthaltes in Princeton das erste allgemein einsetzbare Schnittebenenverfahren, das (zumindest theoretisch) die vollständige Lösbarkeit beliebiger ganzzahliger Programme erlaubte. Auch wenn sich dies praktisch nur teilweise umsetzen ließ, stellte dieses Verfahren einen entscheidenden algorithmischen Fortschritt dar.