B&B-Verfahren

Branch and Bound (B&B)-Verfahren dienen zur Lösung von kombinatorischen und ganzzahligen Optimierungsmodellen. B&B-Verfahren bestehen aus den zwei Komponenten Verzweigung (Branching) sowie Schrankenberechnung und Ausloten (Bounding). Sobald alle im B&B-Baum entstehenden Teilprobleme vollständig verzweigt oder ausgelotet sind, hat das Verfahren eine optimale Lösung gefunden oder festgestellt, dass keine zulässige Lösung existiert.

Ein Beispiel verdeutlicht die Vorgehensweise: Gegeben ist ein Knapsack- Problem mit Nutzenwerten uj und Gewichten gj der Gegenstände j = 1, 2, 3: Das maximale Gesamtgewicht des Rucksacks beträgt ... sie zeigt den B&B-Baum, der sich bei Anwendung des wie folgt ausgestalteten B&B-Verfahrens ergibt:

• Bounding: LP-Relaxation zur Berechnung lokaler oberer Schranken, anfängliche globale untere Schranke LB = 0 (keine zulässige Lösung bekannt)

• Branching: Verzweigung in zwei Teilprobleme durch Setzen von und

• Branching-Regeln: Auswahl jeweils des Gegenstands h (d.h. der Variablen xh), der in der Lösung der LPRelaxation nur unvollständig in den Rucksack passt; Anwendung

der LIFO-Regel Für die Berechnung der oberen Schranke UB0 = 17 im Ausgangsproblem P0 s. LP-Relaxation. In P1 wird eine erste zulässige Lösung mit LB = 13 gefunden. Nach Verzweigen von P2 ergibt sich in P3 eine bessere zulässige Lösung mit LB = 14. P4 wird ausgelotet, da UB4 nicht größer als dieser beste bis dahin bekannte Zielfunktionswert ist. Da nun alle Knoten vollständig verzweigt oder ausgelotet sind, endet das Verfahren. Als optimal wurde damit die in P3 gefundene beste zulässige Lösung erkannt.

<< vorhergehender Begriff

nächster Begriff >>

B

B-Marke