Branch and Bound
Branch and Bound durchsucht den Lösungsraum durch Verzweigung und beschneidet Teilbäume, die das Optimum nicht enthalten können, anhand von Schranken; es wird in der diskreten Optimierung eingesetzt.
Zweck
Kombinatorische Optimierungsprobleme exakt lösen und die Suche durch Pruning beschleunigen.
Mechanismus
Eine globale beste Schranke wird verwaltet. Branching: das Problem in Teilprobleme zerlegen. Bounding: für jedes Teilproblem eine untere/obere Schranke berechnen und es beschneiden, wenn die Schranke die aktuelle Beste nicht übertrifft. Häufig bei ganzzahliger Programmierung und beim TSP.
Anwendungsfälle
- Ganzzahlige Programmierung
- TSP-Lösung
- Kombinatorische Optimierung