BranchandBoundVerfahren

BranchandBoundVerfahren, auch Branch-and-Bound-Verfahren genannt, ist ein globales Optimierungsverfahren zur Lösung von diskreten oder gemischt-ganzzahligen Problemen. Es durchsucht einen Suchbaum, indem es Teilprobleme erzeugt (Branching) und für jedes Teilproblem eine Ober- bzw. Untergrenze des optimalen Werts bestimmt (Bounding). Ein laufender Lösungsvorschlag (Incumbent) dient als Ober- bzw. Untergrenze; wenn ein Teilproblem eine bessere Lösung liefert, wird der Inkumbent aktualisiert. Teilprobleme, deren Grenzwert nicht besser ist als der Inkumbent, werden verworfen (Pruning).

Der Algorithmus setzt sich aus mehreren Bausteinen zusammen: Branching (Aufteilung des Problems in Teilprobleme, z. B. Entscheidung einer Variablen, Wertebereich einschränken), Bounding (Berechnung einer Grenze z. B. durch eine Relaxation wie LP-Relaxation oder andere Abschätzungen), Node-Selection (Auswahl des nächsten zu bearbeitenden Teilbaums, oft Best-First mit Prioritätswarteschlange), Pruning (ausschluss von Teilbäumen aufgrund zu schlechter Bound).

Typische Bounding-Verfahren umfassen relaxierte Probleme (z. B. LP-Relaxation beim gemischt-ganzzahligen Programmieren), Relaxationen bei Rucksack- oder Knotenproblemen. Branching-Strategien betreffen die Wahl der zu teilenden Variablen oder Entscheidungen. Branch-and-Bound ist ein exaktes Verfahren, das in der Praxis oft durch Branch-and-Cut oder Branch-and-Price erweitert wird, um zusätzliche Schnitte oder Spalten zu integrieren.

Anwendungsgebiete umfassen 0-1-Integer-Programmierung, Transport- und Knapsack-Probleme, TSP, Scheduling. Die Komplexität ist im Allgemeinen exponentiell; die Leistungsfähigkeit hängt stark von der Qualität der Bounding-Funktionen, der Topologie des Suchbaums und guten Startlösungen ab. Siehe auch Branch-and-Cut, Cutting-Planes, Integer Programming.