Optimierungsverfahren Glossar

Branch-and-Bound

Branch-and-Bound ist ein exaktes Optimierungsverfahren, bei dem der Lösungsraum rekursiv in Teilräume zerlegt und durch Schrankenbewertungen systematisch reduziert wird, um optimale Lösungen effizienter zu bestimmen. Sie werden insbesondere eingesetzt, wenn ein vollständiges Durchprobieren aller Möglichkeiten zu aufwendig wäre.

Typischer Einsatz bei:

• Traveling Salesman Problem
• Knapsack Problem
• Integer Linear Programming
• Scheduling-/Zuordnungsproblemen

Heuristische Optimierungsverfahren

Heuristische Optimierungsverfahren sind Verfahren zur Lösung von Optimierungsproblemen, die gute bzw. annähernd optimale Lösungen in vertretbarer Zeit finden, ohne eine globale Optimalität garantieren zu müssen. Dabei wird durch vereinfachte Suchstrategien oder erfahrungsbasierte Regeln auf eine vollständige Exploration des Suchraums verzichtet. Ein solches Vorgehen nennt man auch eine approximative Bestimmung.

Sie werden vor allem eingesetzt, wenn:

• der Suchraum sehr groß ist,
• exakte Verfahren zu langsam wären,
• eine „hinreichend gute“ Lösung ausreicht.

Metaheuristische Verfahren Metaheuristische Verfahren sind übergeordnete, allgemein einsetzbare Optimierungsstrategien zur Lösung komplexer Optimierungsprobleme, die heuristische Suchverfahren systematisch steuern und erweitern. Sie dienen dazu, lokale Optima zu vermeiden und den Suchraum effizient zu explorieren.