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 Fachbegriff: B | Nächster Fachbegriff: B-Marke

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Administrationssystem | Einkommenseffekt der Investition Multiplikatoranalyse | Antitrust-Politik

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer