Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Im Unterschied zu linearen Programmen, die beispielsweise mit Innere-Punkte-Verfahren in Polynomialzeit optimal gelöst werden können, ist das Finden einer beweisbaren Optimallösung für ganzzahlige Programme ein NP-schweres Problem. Dies macht sich auch in der Praxis bemerkbar. Während selbst große lineare Programme heute weitgehend mit Standardmethoden gelöst werden können, hängt die Lösbarkeit ganzzahliger Programme sehr viel stärker von den spezifischen Eigenheiten des jeweiligen Planungsproblems und von der gewählten Modellierung ab. Ein Optimierungsproblem mit hundert ganzzahligen Variablen kann aus praktischer Sicht unlösbar sein, während andere Probleme mit tausenden ganzzahliger Variablen innerhalb weniger Sekunden gelöst werden. Es gibt zwar auch in der ganzzahligen Optimierung Standardmethoden, mit denen durch große algorithmische Fortschritte innerhalb der letzten zehn Jahre mittlerweile viele praktische Planungsprobleme als IP gelöst werden können, aber gerade die Lösung großer ganzzahliger Programme in annehmbarer Zeit erfordert oft eine geschickte Modellierung und eine Kombination mehrerer Lösungsverfahren mit problemspezifischen Anpassungen.

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