Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Heuristiken

Für fast jedes Optimierungsproblem lassen sich leicht eine Vielzahl von Heuristiken finden, die für dieses spezielle Problem schnell zulässige Lösungen finden. Dagegen ist die Entwicklung heuristischer Verfahren, die zuverlässig gute Lösungen finden, und das möglichst auch noch für eine ganze Klasse verwandter Optimierungsprobleme und nicht nur für ein spezielles Problem, eine nicht triviale Aufgabe.

Beispiele für problemspezifische Heuristiken beim Problem des Handlungsreisenden sind die Minimum-Spanning-Tree-Heuristik zur Konstruktion einer zulässigen Tour mit Hilfe eines minimal aufspannenden Baumes und die k-Opt-Heuristiken zur Verbesserung einer bereits gefundenen Tour. Dieses Optimierungsproblem ist auch eines der wenigen Beispiele, bei denen sich leicht heuristische duale Schranken angeben lassen. Beispielsweise enthält jede Tour durch n Knoten auch genau n Kanten, so dass eine kürzeste Tour mindestens so lang sein muss wie die Summe der n kürzesten Kantenlängen. Im Allgemeinen ist es deutlich schwieriger, gute duale Schranken anzugeben.

Neben solchen speziell für ein Problem entwickelten Verfahren gibt es sogenannte Metaheuristiken, die auf problemunabhängige Weise Strategien zur Suche zulässiger Lösungen beschreiben. Die einzelnen Schritte dieser Algorithmen müssen allerdings speziell auf das zu lösende Problem angepasst werden. Beispiele hierfür sind das Runden von LP-Lösungen, lokale Suche, Tabu-Suche, Genetische Algorithmen, Simulated Annealing, Variable Nachbarschaftssuche und Ameisenalgorithmen. Einige dieser Verfahren haben Prozesse wie die natürliche Selektion oder das Verhalten von Ameisen auf der Suche nach Futter zum Vorbild; inwieweit das für die Lösungsqualität und die Lösungszeiten in der Praxis von Vorteil ist, ist umstritten.

Als alleiniges Lösungsverfahren haben all diese Algorithmen den Nachteil, dass sie erstens nicht immer eine Lösung finden, und zweitens meistens nichts über die Qualität gefundener Lösungen im Vergleich zu einer Optimallösung bekannt ist. Sie können aber beispielsweise sehr sinnvoll im Rahmen eines Branch and Cut-Ansatzes eingesetzt werden, um an verschiedenen Knoten des Suchbaumes beispielsweise aus der aktuellen LP-Lösung gute zulässige Lösungen zu generieren und so evtl. Teile des Baumes abschneiden zu können.

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