Branch-and-Bound-Verfahren

1. Begriff: Verfahren des Operations Research (OR) zur exakten, d.h. optimalen  Lösung eines (häufig schweren) kombinatorischen Optimierungsproblems (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat).

2. Vorgehensweise: Der Algorithmus verwendet das Prinzip der Aufteilung und Begrenzung des Lösungsraumes. Durch fortwährende Aufteilung des ursprünglichen Problems entsteht eine Baumstruktur, der Branch-and-Bound-Baum. Schritte in jedem Knoten des Baums:
a) Lösung einer Relaxation, häufig der LP-Relaxation, bei der die Ganzzahligkeitsbedingungen auf den Variablen zunächst weggelassen werden. Folgende Fälle können eintreten: i) die Lösung ist ganzzahlig (dann ist ggf. eine neue beste bekannte zulässige Lösung gefunden; der Knoten muss nicht mehr weiter betrachtet werden); ii) die Lösung ist unzulässig, dann muss der Knoten nicht mehr weiter betrachtet werden; iii) die Lösung hat noch fraktionale, d.h. nicht-ganzzahlige Variablenwerte, obwohl diese ganzzahlig sein sollten.
b) Branch (Verzweigung): Eine fraktionale Variable wird ausgewählt und zwei neue Teilprobleme gebildet, indem dieser Variablen einmal der nächstgrößere ganzzahlige Wert zugewiesen wird und einmal der nächstkleinere ganzzahlige Wert. Die Auswahl der Variablen erfolgt durch eine Verzweigungsregel (Branchingregel).
c) Bound (Schranke): Falls die aus der Relaxation gewonnene (sog. duale) Schranke schlechter (d.h. bei einem Minimierungsproblem größer) ist als der Wert einer besten bisher bekannten zulässigen Lösung (sog. primale Schranke), muss der Knoten nicht mehr weiter betrachtet werden. Das Optimum ist erreicht, wenn keine Knoten des Baum mehr offen sind, d.h. noch fraktionale Variablen aufweisen, aber noch nicht verzweigt wurde.

Die Laufzeit eines Branch-and-Bound-Verfahrens hängt wesentlich von der Qualität der Schranken ab. Für die primale Schranke werden zusätzlich Heuristiken eingesetzt, die duale Schranke hängt von der Qualität der Relaxation ab und wird oft durch zusätzliche Schnittebenen verschärft. Im schlimmsten Fall entartet der Algorithmus zu einer vollständigen Enumeration.

3. Anwendung: Prinzipiell ist der Algorithmus u.a. auf alle diskreten Probleme anwendbar, v.a. auf gemischt-ganzzahlige Programme oder das Traveling-Salesperson-Problem.