Ganzzahlige Optimierung (englisch Integer Programming, kurz ILP für Integer Linear Programming) löst Optimierungsprobleme, bei denen einige oder alle Entscheidungsvariablen nur ganzzahlige Werte annehmen dürfen. Während die Lineare Optimierung kontinuierliche Variablen erlaubt und effizient lösbar ist, wird die ganzzahlige Variante schnell NP-schwer — genau diese Härte macht sie aber auch so ausdrucksmächtig: Viele praktische Probleme lassen sich als ILP formulieren.
Ganzzahlig vs. kontinuierlich
Ein lineares Programm minimiert eine Zielfunktion unter linearen Nebenbedingungen, wobei die Variablen reelle Werte annehmen. Ein ILP erzwingt zusätzlich Ganzzahligkeit, zum Beispiel x₁, x₂ ∈ ℤ oder binäre Variablen x ∈ {0, 1} für Ja/Nein-Entscheidungen. Diese scheinbar kleine Einschränkung ändert die Komplexität fundamental: Die LP-Relaxation (Ganzzahligkeitsbedingung weglassen) ist polynomial lösbar, das ILP selbst ist im Allgemeinen NP-vollständig. Bei einem gemischt-ganzzahligen Programm (MILP) sind nur einige Variablen ganzzahlig, die übrigen bleiben kontinuierlich.
Was sich als ILP modellieren lässt
- Binäre Variablen kodieren Entscheidungen: Baue ich Standort A oder nicht? Startet Schicht B oder nicht?
- Set Cover und Vertex Cover sind 0/1-ILPs: Set Cover wählt Teilmengen, bis jedes Element überdeckt ist.
- Das Rucksackproblem ist das einfachste 0/1-ILP überhaupt: wähle Gegenstände, deren Gesamtgewicht die Kapazität nicht überschreitet.
- Rundreisen, Personaleinsatz, Transport- und Zuordnungsprobleme lassen sich als ganzzahlige Programme formulieren.
Lösungsverfahren
In der Praxis dominiert Branch and Bound: Das Problem wird in Teilprobleme verzweigt, und die LP-Relaxation liefert für jedes Teilproblem eine Schranke, mit der man ganze Zweige abschneiden kann. Schnittebenen (Cutting Planes) ergänzen Nebenbedingungen, die unzulässige Bruchlösungen ausschließen, ohne zulässige ganzzahlige Lösungen zu verlieren. Moderne Solver kombinieren beides zu Branch and Cut. Standardwerkzeuge sind CPLEX, Gurobi, SCIP sowie Open-Source-Bibliotheken wie Google OR-Tools und PuLP.
Strukturen, die sich weigern, schwer zu sein
Nicht jedes ILP ist schwer: Besitzt die Koeffizientenmatrix eine total unimodulare Struktur, hat die LP-Relaxation automatisch ganzzahlige Ecken — das Problem ist dann polynomial lösbar, etwa viele Transport- und Zuordnungsprobleme. Die Kunst der Modellierung besteht oft darin, solche Strukturen zu erkennen oder herzustellen. Für schwere Instanzen greifen heuristische Verfahren wie Metaheuristiken oder der Genetische Algorithmus.
Verwandte Grundlagen: Lineare Optimierung, Simplex-Verfahren, Rucksackproblem, Exakte Überdeckung, NP-Vollständigkeit.