Ganzzahlige lineare Optimierung

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. integer (linear) programming), 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.^[1]

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.

1. ↑ Robert E. Bixby: A brief history of linear and mixed-integer programming computation. In: Optimization Stories. EMS Press, 2012, ISBN 978-3-936609-58-5, S. 107–121 (uni-bielefeld.de [PDF; abgerufen am 4. Januar 2024]).