Ein Optimierungsverfahren, das ganzzahlige Entscheidungsvariablen auswählt, um eine lineare Zielfunktion unter einer endlichen Menge linearer Gleichungs- und Ungleichungsnebenbedingungen zu maximieren oder zu minimieren.

Prinzip

Durch die Ganzzahligkeitsbedingung ist die Menge zulässiger Lösungen eine diskrete Teilmenge des Polyeders der linearen Relaxation; optimale ganzzahlige Lösungen werden durch Erkundung dieser diskreten Menge mittels Verzweigung, Schnitten oder Enumeration unter Nutzung linearer Schranken ermittelt.

Demonstration

Situation: Eine Produktionsanlage weist ganze Maschinen (0 oder 1) zwei Produkten zu unter Kapazitäts- und Nachfragebeschränkungen. Erkennung: Variablen stellen Maschinenzahlen dar und müssen ganzzahlig sein. Handlung: Formulierung des linearen Gewinnziels, lineare Kapazitätsnebenbedingungen und Lösung mit Branch-and-Bound auf der LP-Relaxation. Folge: Der Solver liefert eine ganzzahlige Zuordnung, die den Gesamtgewinn maximiert und alle Beschränkungen erfüllt.

Fehlanwendung

ILP mit der Lösung des kontinuierlichen LP gleichsetzen und das kontinuierliche Optimum einfach auf Ganzzahlen runden. Der semantische Fehler besteht darin zu glauben, dass gerundete Lösungen ganzzahlig zulässig und optimal sind; Runden kann Nebenbedingungen verletzen und zu suboptimalen oder unzulässigen Lösungen führen.

Konsequenz

Korrekte Anwendung liefert umsetzbare, ganzzahlig zulässige Pläne und gültige Optimalitätsschranken; falsche Anwendung (naives Runden) kann unzulässige Zeitpläne, verletzte Beschränkungen, unerwartete Kosten oder überschätzte Zielfunktionswerte zur Folge haben.

Umkehrung

Wenn Entscheidungsvariablen nichtlinear interagieren (Produkte ganzer Variablen) oder wenn Bruchteillösungen interpretativ zulässig sind (z. B. erwartete Anteile in stochastischen Modellen), gelten die Standardannahmen der ILP nicht und es werden gemischt-ganzzahlige nichtlineare oder stochastische Modelle erforderlich.

Abgrenzung

Eindeutig darin: Ein Standortproblem mit binären Öffnungs-/Schließvariablen und linearen Kapazitätsbeschränkungen. Randfall: Große Zählvariablen, bei denen die LP-Relaxation enge Schranken liefert, aber spezielle Schnitte nötig sind. Eindeutig außen: Ein ganzzahliges Optimierungsproblem mit nichtlinearem Ziel oder nichtlinearen Nebenbedingungen (keine ILP).

Semantische Spannung

Optimalität ↔ Berechenbarkeit — Ganzzahligkeit liefert exakte, ausführbare Lösungen, erhöht jedoch die Rechenkomplexität gegenüber kontinuierlichen Relaxationen.

Synthese

ILP trennt die operative Umsetzbarkeit diskreter Entscheidungen vom konvexen, kontinuierlichen Optimierungsraum; effizientes Lösen nutzt LP-Schranken, Verzweigung und Schnitte, um kombinatorische Komplexität zu beherrschen.