Siehe auch: Entscheidungsbaum
Typ von Entscheidungsbaumverfahren der kombinatorischen
Optimierung, zur Klasse der
impliziten vollständigen Enumeration gehörend. Es wurde erstmals 1960 von Lana und Doig für Aufgaben der ganzzahligen Optimierung
entwickelt. Der Name wurde 1963 durch John D. C. Little u.a. im Zusammenhang mit dem Traveling-Salesman
Problem eingeführt.
Mit diesem Verfahren wird die Menge aller Lösungen systematisch in
Untermengen zerlegt (Branch), und die Untermengen werden bewertet (Bound) mit
dem bestmöglichen Wert der Zielfunktion, der gerade noch erreichbar erscheint.
Dabei wird jeweils die Lösungsuntermenge mit dem günstigsten Zielfunktionswert (Bound)
weiter aufgespalten. Das Verfahren bricht ab, wenn in der zur weiteren
Aufspaltung ausgewählten Lösungsuntermenge eine vollständige Lösung bekannt
ist, deren Zielfunktionswert mit dem berechneten Bound identisch ist.
Sowohl in der Organisation des Baumes als auch in der Terminologie
unterscheidet sich Branch and Bound von den prinzipiell verwandten Verfahren
der begrenzten Enumeration und der dynamischen Optimierung.
Ein
typischer Entscheidungsbaum des Branch and Bound sei an einem Beispiel vom Typ Knapsack-Problem
dargestellt. Es stehe eine Finanzsumme von 30 Mio. DM zur Verfügung, die für
eine Auswahl aus den fünf Projekten A bis E zu verwenden sei. Der Nutzen
dieser Projekte (z. B. in Form von Erlösen) und die erforderlichen Finanzmittel
(in Mio. DM) sind in der folgenden Tabelle genannt. Gefragt ist, welche
Projekte auszuwählen sind, um mit den verfügbaren 30 Mio. DM eine maximale
Nutzensumme zu erzielen.
Der Lösungsprozeß ist als Baum der impliziten vollständigen
Enumeration dargestellt. Der Start-Knoten enthält sämtliche 2 = 32 (im einzelnen unbekannte) Lösungen. Diese Menge wird
schrittweise in Untermengen aller Lösungen zerlegt, die ein bestimmtes Projekt
enthalten (Buchstabe) bzw. nicht enthalten (Buchstabe mit Strich). Die Zweige A
und X repräsentieren disjunkte Untermengen mit jeweils 16 Lösungen. Die
Untermengen der Zweige AB und
AB
enthalten jeweils acht Lösungen,
die Zweige ABC und ABC jeweils vier Lösungen .
Die optimale Lösung lautet ABCDE mit der Nutzensumme von 94 und der
Auswahl der Projekte A, C und E. Diejenigen Zweige des Baumes mit kleineren
Nutzensummen als 94 brauchen nicht weiter betrachtet zu werden, da sie zu
keiner besseren als der gefundenen Lösung führen können.
Jeder
Zweig des Baumes wurde durch einen "Bound" (hinter dem Doppelpunkt) bewertet.
Dieser wurde durch die Lösung eines relaxier- ten Problems (Entscheidungsbaumverfahren)
bestimmt. Dazu wurde die Bedingung, daß nur ganze Projekte ausgewählt werden
können, ersetzt durch die weichere Bedingung, daß auch Projektteilungen
zulässig sind (Knapsack-Problem).
Zur Lösung eines so "relaxierten" Problems braucht man nur die Projekte in abnehmender
Reihenfolge des Quotienten "Nutzen/Finanzmittel" auszuwählen, bis die
verfügbaren 30 Mio. DM verbraucht sind, wobei das letztgewählte Projekt
gewöhnlich nur zu einem Teil realisiert werden kann, z.B. A ganz, B ganz und C
zu 90% mit einer Nutzensumme von 42 + 30 + 0,9 32 = 100,8, gerundet auf 100.
Für den Zweig AB führen A ganz, C ganz und 8/11 von D zu der Nutzensumme von
95,82, gerundet auf 95. Wenn die Lösung des relaxierten Problems keine
geteilten Projekte enthält, liegt mit ihr für den entsprechenden Zweig des
Baumes die jeweilige Bestlösung des ursprünglichen Problems vor, so daß von
hier aus keine weitere Verzweigung mehr erforderlich ist. Das gilt z. B. für
die Zweige Ä (B ganz, C ganz, D ganz) und ABC (A ganz, C ganz, E ganz).
Literatur: Land,
A. H.IDoig, A. G., An
Automatic Method of Solving Discrete Programming Problems, in: Econometrica,
28. Jg. (1960), S. 497ff. Little, J. D. C. u.a., An Algorithm for the Traveling Salesman
Problem, in: Operations Research, 11. Jg. (1963), S. 972ff.
Vorhergehender Fachbegriff: Brainwriting-Pool | Nächster Fachbegriff: Branch-and Cut-Algorithmen
Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken
|
