Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Exakte und heuristische Verfahren

Bei der Klassifizierung der Algorithmen ist zu unterscheiden zwischen exakten und heuristischen Lösungsverfahren.

Heuristische Verfahren liefern typischerweise zulässige Lösungen in relativ kurzer Zeit, aber keine Information darüber, wie gut diese im Vergleich zu einer Optimallösung sind. Wenn eine Heuristik keine Lösung findet, ist nicht bekannt, ob dies am Algorithmus liegt oder ob das betrachtete Optimierungsproblem prinzipiell unlösbar ist. Heuristische Verfahren sind meist an das zu lösende Problem angepasst, wie beispielsweise die k-Opt-Heuristiken für das Problem des Handlungsreisenden. Bei Metaheuristiken wie Tabu-Suche ist zwar der grundsätzliche Ablauf generisch, aber die einzelnen Schritte des Algorithmus müssen abhängig vom betrachteten Problem definiert werden.

Exakte Verfahren finden beweisbar stets eine optimale Lösung oder stellen fest, dass das Problem unlösbar oder unbeschränkt ist, vorausgesetzt, man lässt den Algorithmus beliebig lange laufen. Beispiele hierfür sind Branch-and-Bound, Schnittebenenverfahren sowie deren Kombination Branch-and-Cut. In der Praxis kann man diese Verfahren durch Anpassung an das zu lösende Problem und durch Kombination mit Heuristiken oft deutlich beschleunigen.

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