Ganzzahlige lineare Optimierung

Geschichte

Der Beginn der ganzzahligen Optimierung hängt eng mit der Entwicklung der linearen Optimierung Mitte der 1940er Jahre zusammen. Im Jahre 1947 veröffentlichte George Dantzig mehrere entscheidende Arbeiten zur Linearen Optimierung und zum Simplex-Verfahren, die er in den darauffolgenden Jahren zusammen mit John von Neumann und anderen weiterentwickelte.

Als mit dem Aufkommen von Computern in den 1950er Jahren die ersten praktisch einsetzbaren Computerprogramme zur Lösung linearer Programme entwickelt wurden, rückte auch die Lösbarkeit ganzzahliger Optimierungsprobleme in erreichbare Nähe. Mitte der 1950er Jahre arbeiteten D. R. Fulkerson, G. Dantzig, und S. Johnson an ersten Schnittebenen für das Problem des Handlungsreisenden. Ohne Kenntnis dieser Arbeiten und motiviert durch ehemalige Kollegen der US Navy, die an ganzzahligen Lösungen interessiert waren, entwickelte Ralph Gomory im Jahre 1958 während seines Aufenthaltes in Princeton das erste allgemein einsetzbare Schnittebenenverfahren, das (zumindest theoretisch) die vollständige Lösbarkeit beliebiger ganzzahliger Programme erlaubte. Auch wenn sich dies praktisch nur teilweise umsetzen ließ, stellte dieses Verfahren einen entscheidenden algorithmischen Fortschritt dar.

Kurz danach, im Jahre 1960, stellten A. H. Land und A. G. Doig das Branch-and-Bound-Verfahren vor, das auf einer geschickten Enumeration des Suchraumes basiert. 1965 gab R. J. Dakin einen einfach implementierbaren Algorithmus dazu an. Später wurde Branch-and-Bound mit Schnittebenenverfahren zu Branch-and-Cut kombiniert, was die Lösung deutlich größerer ganzzahliger linearer Programme erlaubte.

In den 1980er Jahren arbeiteten Manfred Padberg und andere an Schnittebenen für oft auftauchende Teilstrukturen wie Rucksackprobleme, die oft auch in allgemeinerem Kontext eingesetzt werden können. Die enormen algorithmischen Fortschritte in der linearen Optimierung in den 1990er Jahren schlugen sich auch in einer deutlich besseren Lösbarkeit ganzzahliger Programme nieder, da beispielsweise bei der Anwendung von Schnittebenenverfahren und Branch-and-Bound-Algorithmen sehr viele lineare Programme gelöst werden müssen. Neben besseren Modellierungen und Lösungstechniken für häufig auftauchende Teilprobleme, wie beispielsweise Netzwerkflüsse, wurden parallel dazu viele Heuristiken, also Näherungsverfahren, entwickelt, die meist in kurzer Zeit zulässige Lösungen berechnen. Sie können u. a. auch als Teil von Branch-and-Cut-Verfahren eingesetzt werden, um diese zu beschleunigen. All diese Verfahren sind noch Gegenstand aktueller Forschung.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ganzzahlige lineare Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung