Branch-and-Bound-Verfahren

1. Begriff: Verfahren des Operations Research (OR), bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder Enumerationsverfahren (Entscheidungsbaumverfahren) wegen des Rechenaufwandes ausscheiden. Lässt sich das Problem durch n diskrete Variablen, die jeweils k mögliche Werte annehmen können formulieren, dann liegt eine Interpretation als qualitatives Entscheidungsproblem nahe.

2. Vorgehensweise: Das Lösungsverfahren verwendet das Prinzip der Aufteilung und Begrenzung des Lösungsraumes, um eine vollständige Enumeration zu vermeiden. Schritte: a) Branch (Verzweigung): Einer der Variablen wird ein bestimmter zulässiger Wert zugeordnet, wodurch ein neues Unterproblem entsteht, dessen Umfang um eine Variable geringer ist. Bei k möglichen Werten für die ausgewählte Variable entstehen so k „einfachere” Unterprobleme. Es bleibt festzustellen, welches der Unterprobleme die optimale Lösung enthält.

b) Bound (Schranke): Nach der Fixierung einer Variablen wird ermittelt, wie die Lösung für die restlichen Variablen günstigenfalls ausfallen kann. Hat man für alle möglichen Werte einer ausgewählten Variablen die Bounds ermittelt, so wählt man die Alternative mit dem günstigsten Bound, um zur nächsten Verzweigung weiterzugehen. Wird nach mehrmaligem Branching und Bounding eine zulässige Lösung erreicht, so können alle Fälle mit ungünstigeren Bounds gestrichen werden. Das Optimum ist erreicht, wenn keine günstigere zulässige Lösung mehr zu erwarten ist.

Die Güte eines Branch-and-Bound-Verfahrens hängt wesentlich von der Auswahl der Bounds ab. Diese Auswahl kann nur heuristisch erfolgen; es ist deshalb nicht möglich, über die Konvergenz des Algorithmus Aussagen zu machen.

3. Anwendung: Prinzipiell ist das Verfahren auf alle diskreten Probleme anwendbar, v.a. auf Zuordnungs- und Travelling-Salesman-Probleme.