Ganzzahlige Programmierung (IP)

Die ganzzahlige Programmierung (pure IP) ist die Problemklasse min c^T x s.t. Ax ≤ b, x ∈ Z^n_+ in kanonischer Form, in der alle Entscheidungsvariablen ganzzahlig sind. Der 0-1-Spezialfall x ∈ {0,1}^n ist die natürliche Formulierung der kombinatorischen Optimierung: Rucksack, Zuordnung, Set Covering, Set Partitioning, Traveling Salesman Problem (TSP), Matching und Graphfärbung. Komplexität: pure IP erscheint als 0-1-IP in Karps Liste der 21 NP-vollständigen Probleme (1972); Lenstra (1983) zeigte, dass IP in fester Dimension in polynomieller Zeit lösbar ist (praxisuntauglich, wenn die Dimension Teil der Eingabe ist). Wird die Ganzzahligkeit der LP-Relaxation auferlegt, kann sich der Optimalwert deutlich ändern; der Integrality Gap ist das kanonische Maß für die Stärke der Formulierung. Der klassische Algorithmus ist Gomorys (1958) Schnittebenenverfahren: LP-Relaxation lösen, bei fraktionalem Optimum mittels Simplex-Tableau einen Gomory-Schnitt erzeugen, der das aktuelle LP-Optimum, aber keinen ganzzahligen Punkt ausschließt, hinzufügen und erneut lösen; dies terminiert nach endlich vielen Iterationen am ganzzahligen Optimum (theoretisch). In der Praxis sind Land und Doigs (1960) Branch-and-Bound und später Branch-and-Cut (Padberg und Rinaldi 1991) schneller. Polyedertheorie — Chvátal (1973), Schrijver (1986) — leitet gültige Ungleichungen (Subtour-Eliminierung und Blossom-Ungleichungen beim TSP) ab, die die Relaxation an die konvexe Hülle der ganzzahligen Punkte annähern. Anwendungen: TSP / Tourenplanung (Dantzig, Fulkerson, Johnson 1954), Zuordnung, Scheduling, Netzflüsse, Cutting Stock (Gilmore und Gomory 1961), Bin Packing.