Ganzzahlige Programmierung

Ganzzahlige Programmierung (GP; englisch: integer programming, IP) ist ein Teilgebiet der mathematischen Optimierung, das sich mit Problemen befasst, bei denen einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen.

Der am besten untersuchte Spezialfall ist die ganzzahlige lineare Programmierung (GLP; englisch: integer linear programming, ILP), bei der die Zielfunktion und die Nebenbedingungen linear sind. Im Gegensatz zur linearen Programmierung, bei der die Variablen beliebige reelle Werte annehmen können, macht die Ganzzahligkeitsbedingung GP-Probleme erheblich schwieriger zu lösen.

Die ganzzahlige Programmierung findet breite Anwendung in der Wirtschaft, Logistik, Produktionsplanung und anderen Bereichen, in denen die Variablen von Natur aus diskret sind (z. B. die Anzahl der produzierten Einheiten oder die Anzahl der Mitarbeiter).

Definition und Terminologie

Ein allgemeines Problem der ganzzahligen linearen Programmierung kann wie folgt formuliert werden:

Gesucht ist ein Vektor $x$, der:

$c^{T}x$ maximiert (oder minimiert)

unter den Nebenbedingungen:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (alle Komponenten des Vektors $x$ sind ganze Zahlen)

wobei $x$ der Vektor der Variablen, $c$ und $b$ Vektoren und $A$ die Koeffizientenmatrix ist.

Je nach den Anforderungen an die Variablen werden folgende Problemtypen unterschieden:

• Rein ganzzahlige Programmierung: Alle Variablen müssen ganzzahlig sein.
• Gemischt-ganzzahlige Programmierung (englisch: mixed-integer programming, MIP): Nur ein Teil der Variablen muss ganzzahlig sein.
• Binäre (0-1) Programmierung: Die Variablen können nur die Werte 0 oder 1 annehmen, was die Modellierung von logischen Entscheidungen des Typs «Ja/Nein» ermöglicht.

Wichtige Eigenschaften und Komplexität

Berechnungskomplexität

Das Problem der ganzzahligen linearen Programmierung ist im Allgemeinen NP-schwer. Das bedeutet, dass kein bekannter Algorithmus existiert, der eine exakte optimale Lösung für ein beliebiges GP-Problem in polynomialer Zeit finden kann. Die Komplexität ergibt sich aus der kombinatorischen Natur des Problems, da die Anzahl der möglichen ganzzahligen Lösungen mit der Anzahl der Variablen exponentiell ansteigen kann.

Beziehung zur linearen Programmierung (LP-Relaxation)

Für jedes GP-Problem kann eine lineare Relaxation formuliert werden — ein Problem der linearen Programmierung (LP), bei dem die Ganzzahligkeitsbedingung für die Variablen fallengelassen wird. Die Lösung der LP-Relaxation hat zwei wichtige Eigenschaften:

1. Sie lässt sich deutlich schneller (in polynomialer Zeit) lösen.
2. Der optimale Wert der Zielfunktion der LP-Relaxation liefert eine Schranke (eine obere Schranke für ein Maximierungsproblem und eine untere für ein Minimierungsproblem) für den optimalen Wert des ursprünglichen ganzzahligen Problems.

Das einfache Runden der gebrochenen Lösung der LP-Relaxation auf die nächsten ganzen Zahlen führt jedoch in der Regel nicht zu einer optimalen oder sogar zulässigen Lösung des ganzzahligen Problems.

Eigenschaft der totalen Unimodularität

Es gibt eine wichtige Klasse von GLP-Problemen, die sich genauso leicht lösen lassen wie ihre LP-Relaxationen. Dies sind Probleme, bei denen die Nebenbedingungsmatrix $A$ total unimodular ist (d. h., die Determinante jeder ihrer quadratischen Untermatrizen ist 0, +1 oder −1). Wenn die Matrix $A$ total unimodular ist und der Vektor $b$ ganzzahlig ist, sind alle Ecken des Polyeders der zulässigen Lösungen der LP-Relaxation automatisch ganzzahlig. Folglich ist die mit dem Simplex-Verfahren gefundene Lösung ganzzahlig. Beispiele für solche Probleme sind das Transportproblem und das Zuordnungsproblem.

Lösungsmethoden

Zur Lösung allgemeiner GP-Probleme, die nicht die Eigenschaft der totalen Unimodularität besitzen, wurden exakte Methoden entwickelt, die auf der Idee der impliziten Enumeration basieren.

• Branch-and-Bound-Verfahren (englisch: Branch and Bound) — das wichtigste exakte Verfahren, das auf der systematischen Aufteilung der Menge der zulässigen Lösungen in Teilmengen (Verzweigung) und dem Verwerfen (Abschneiden) jener Teilmengen basiert, die nachweislich keine optimale Lösung enthalten. Zur Bewertung der Teilmengen wird die LP-Relaxation verwendet.

• Schnittebenenverfahren (Gomory-Verfahren; englisch: Cutting Plane Method) — ein iterativer Ansatz, der dem Problem schrittweise neue lineare Nebenbedingungen («Schnitte») hinzufügt. Diese Schnitte «schneiden» gebrochene Lösungen der LP-Relaxation ab, ohne zulässige ganzzahlige Lösungen zu eliminieren, wodurch der zulässige Bereich der LP-Relaxation schrittweise an die konvexe Hülle der ganzzahligen Lösungen angenähert wird.

Moderne Löser (Solver) verwenden in der Regel hybride Algorithmen wie das Branch-and-Cut-Verfahren (englisch: Branch and Cut), das die Vorteile beider Ansätze kombiniert.

Beispiele und Anwendungsbereiche

Die ganzzahlige Programmierung ermöglicht die Modellierung zahlreicher klassischer Probleme der kombinatorischen Optimierung.

• Rucksackproblem: Ein klassisches Problem der 0-1-Programmierung, bei dem eine Auswahl von Gegenständen mit maximalem Gesamtwert getroffen werden muss, ohne eine Obergrenze für das Gesamtgewicht zu überschreiten.
• Problem des Handlungsreisenden: Die Aufgabe, die kürzeste Route zu finden, die eine gegebene Menge von Städten durchläuft. Es kann als ganzzahliges Programmierungs-Problem formuliert werden, bei dem Variablen die Aufnahme von Kanten des Graphen in die endgültige Route steuern.

Dank ihrer Flexibilität ist die GP eines der gefragtesten Werkzeuge im Operations Research und findet Anwendung in Bereichen wie:

• Logistik und Supply-Chain-Management: Optimierung von Transportrouten, Standortplanung für Lagerhäuser, Bestandsmanagement.
• Produktionsplanung: Erstellung von Produktionsplänen, Ressourcenzuweisung, Maschinenauslastung.
• Finanzwesen und Wirtschaft: Portfolio-Optimierung, Kapitalbudgetierung.
• Telekommunikation und Energiewirtschaft: Planung von Kommunikationsnetzen, Einsatzplanung von Kraftwerksblöcken.

Siehe auch

• Lineare Programmierung
• Branch-and-Bound-Verfahren
• Optimierung