Branch and Bound

Im Gegensatz zu Teile und Herrsche sowie dem dynamischen Programmieren gibt es bei Branch and bound (Verzweige und Begrenze) keine Zerlegung des Gesamtproblems in (einfachere) Teilprobleme. Es wird vielmehr gefordert, dass sich der Lösungsraum baumartig darstellen lässt, s. Abb. 1.

Bei der systematischen Suche nach einer Lösung in einer sehr großen Menge von Kandidaten ist es jedoch gar nicht möglich, einen vollständigen Lösungsbaum zu speichern: Man stelle sich z.B. ein 0/1-Rucksackproblem mit 50 Gegenständen vor. Bei diesem gibt es über eine Billiarde potentielle Belegungen, die nicht alle geprüft werden können.

Wenn eine vollständige Traversierung des Suchbaums nicht möglich ist, ist eine andere Herangehensweise gefragt.

Wie von der Tiefensuche bekannt ist, kann die Menge der Kandidaten (alle Blätter im durch die Wurzel repräsentierten Suchbaum) systematisch in kleinere Teilmengen (Blätter unterhalb eines Knotenzweigs) unterteilt werden. Durch dieses Verzweigen (branch) entstehen Teilmengen, die jeweils unterschiedliche spezielle Eigenschaften besitzen. Die Gegenstandsmenge beim 0/1-Rucksackproblem kann z.B. in die Teilmenge A (alle Rucksackbelegungen, bei denen Gegenstand 1 enthalten ist) und die Teilmenge B (alle Rucksackbelegungen, bei denen Gegenstand 1 nicht enthalten ist) verzweigt werden. Diese Mengen können nun wieder verzweigt bzw. in noch kleinere Teilmengen unterteilt werden bezüglich des Enthaltens der anderen Gegenstände. So entsteht ein typischer vollständiger Suchbaum.

Anstatt den Suchbaum vollständig zu durchlaufen, kann man sich die Frage stellen, welche Knoten es überhaupt wert sind, weiter verfolgt zu werden. Möglicherweise ist die Chance, die Lösung unterhalb eines bestimmten Knotens zu finden, größer als bei einem anderen. Vielleicht ist es sogar unmöglich, dass sich die Lösung unterhalb eines bestimmten Knotens befindet. In diesem Fall kann durch Begrenzen (bound) eine Expansion solcher Knoten unterbunden werden. Um eine derartige Entscheidung treffen zu können, ist es notwendig, Informationen, die an einem Knoten bereits vorliegen oder einfach ermittelt werden können, genau zu analysieren.

Die generelle Vorgehensweise beim Entwickeln eines Branch and Bound Algorithmus' beinhaltet zunächst den Entwurf des Suchbaums. Da am Ende nur die Blätter (die möglichen Lösungen) interessant sind, kann der Baum oberhalb dieser Blätter beliebig gestaltet werden. Des Weiteren wird eine Bewertungsfunktion benötigt. Diese muss für einen Knoten (Bearbeitungszustand) entscheiden, ob dieser (falls möglich) expandiert oder zurückgestellt werden soll. Zur effektiven Begrenzung ist es notwendig, möglichst schnell zu guten Teillösungen zu gelangen, um dadurch bessere Schranken für die Bewertungsfunktion zu erhalten.

Sind diese drei Eigenschaften optimal aufeinander abgestimmt, kann die Suche nach einer Lösung sehr viel effizienter sein, als bei Betrachtung des gesamten Lösungsbaums mit Tiefen- oder Breitensuche. Dies ist aber nicht zwangsläufig der Fall. Können z.B. keine Knoten ausgeschlossen werden, dann wird praktisch eine vollständige Suche durchgeführt, die durch die zusätzliche Bewertung am Ende sogar aufwendiger ist als z.B. eine einfache Tiefensuche. Oder wenn die Berechnung der Bewertungsfunktion ineffizient ist, könnte der dadurch entstehende Verlust den Gewinn durch die Begrenzung aufheben oder gar übersteigen.

0/1-Rucksackproblem

Für ein 0/1-Rucksackproblem mit 4 Gegenständen könnte genau der in Abb. 1 dargestellte Suchbaum entstehen.

Auf jeder Ebene wird für einen bestimmten Gegenstand die Entscheidung getroffen, ob dieser im Rucksack enthalten sein soll oder nicht. Wurden 4 Entscheidungen getroffen, steht eine mögliche Rucksackbelegung fest. Diese kann nun die Lösung (Optimum) sein oder auch nicht.

Im Unterschied zu dem weiter unten bearbeiteten Rundreiseproblem wird beim 0/1-Rucksackproblem eine Auswahl von (einzupackenden) Gegenständen vorgenommen, während beim Rundreiseproblem alle Städte in der Lösung vorkommen müssen.

Statische Begrenzung

Um diesen Baum zu begrenzen, muss für einen expansionsfähigen Knoten (teilgepackter Rucksack; noch nicht voll) entscheiden werden, ob die Lösung prinzipiell unter diesem zu finden sein könnte. Beim Rucksackproblem bietet die Kapazität des Rucksacks eine solche.

Die ja/nein-Angaben an den Kanten/Pfeilen beziehen sich auf die Knoten, von denen sie ausgehen.

Für vier Gegenstände mit den Gewichten (5,4,3,2) und einer Maximalkapazität von 8 können die Zweige ignoriert werden, bei denen die Kapazitätsgrenze überschritten wird (grau). Von 16 möglichen Lösungskandidaten (Blätter) bleiben noch 10 übrig und anstatt 15 Expandierungen vorzunehmen, sind nur noch 9 erforderlich.

Dynamische Begrenzung

Die Kapazitätsgrenze ist eine statische Schranke, denn sie ändert sich während der Suche nicht. Sie gehört hier zur Aufgabenstellung.

Für das Branch and Bound Verfahren sind dynamische Schranken, die im Verlauf der Suche immer strenger werden, von Interesse. Wurde z.B. bereits irgendeine gültige Rucksackbelegung gefunden, können Knoten unter denen nur schlechtere Belegungen zu finden sind, ignoriert werden. Je besser der aktuell beste Rucksack im Verlauf der Suche wird, umso strenger wird die Schranke und umso stärker fällt die Begrenzung aus. Das Ziel ist also möglichst schnell zu einer guten (noch nicht optimalen) Lösung zu gelangen, um von einer möglichst starken Begrenzung zu profitieren.

Gibt es z.B. bereits einen gültigen Rucksack mit einem gewissen Wert, so müsste für einen Knoten (quasi einen noch nicht fertig gefüllten Rucksack) bestimmt werden, ob überhaupt noch ein gültiger Rucksack zusammengestellt werden kann, der wertvoller ist. An jedem Knoten hat der untersuchte Teil-Rucksack einen momentanen Wert und eine Restkapazität. Um zu bestimmen, welcher zusätzliche Wert unter Verbrauch der Restkapazität noch hinzugefügt werden kann, müsste allerdings ein weiteres (kleineres) Rucksackproblem gelöst werden. Die Effizienz einer Bewertungsfunktion ist aber entscheidend. Diese Effizienz kann dadurch erreicht werden, dass eine weniger genaue Schranke ermittelt wird. Für das 0/1 Rucksackproblem bietet sich z.B. folgende Möglichkeit:

Die n Gegenstände mit den Werten w_i und den Gewichten g_i für 1 \leq i \leq n können nach ihrem spezifischen Wert \frac{w_i}{g_i} sortiert entschieden werden. Dieser Quotient sagt aus, welcher Wert pro Gewichtseinheit beim Hinzufügen dieses Gegenstands hinzugewonnen wird. Entscheidungen für Gegenstände mit hohem Wert und geringem Gewicht werden so zuerst getroffen. Es ist sichergestellt, dass \frac{w_i}{g_i} \geq \frac{w_{i+1}}{g_{i+1}}. Für einen Knoten (einen Teil-Rucksack) bei dem bereits k Gegenstände entschieden wurden, kann bei gegebener Maximalkapazität K die Restkapazität r und der damit einhergehende maximal erreichbare Rucksackwert m bestimmt werden. Ein (Teil-)Rucksack ist definiert durch den Vektor \overrightarrow{x}=(x_1, x_2, \dots, x_k) \text{ für } 1 \leq k \leq n \text{ und } x_k \in \{0,1\}. Der Rucksack (1,0,1) enthält demnach Gegenstand 1 und 3 und nicht Gegenstand 2.

Die Restkapazität r eines Rucksacks ist die Differenz zwischen Maximalkapazität K und aktuellem Rucksackgewicht. Der maximal erreichbare Rucksackwert m (obere Schranke für das tatsächliche Maximum) ist die Summe aus dem aktuellen Rucksackwert und der Restkapazität multipliziert mit dem spezifischen Wert des nächsten noch nicht entschiedenen Gegenstands (k+1). Da die spezifischen Werte aller weiteren Gegenstände maximal genauso groß sind, bildet m eine obere Schranke. Liegt der Wert des momentan besten Rucksacks bereits über diesem maximal erreichbaren Wert, so kann der entsprechende Knoten ignoriert werden.

Ablauf

Der mögliche Wertzugewinn kann so für jeden Knoten sehr einfach berechnet werden. Obiges Bild zeigt die entsprechenden Zugewinne an den Knoten für die rechts aufgelisteten Gegenstände. Wie effektiv die resultierende Begrenzung ist, hängt nun von der Reihenfolge ab in der die Knoten geprüft werden. In jedem Fall muss bei Knoten A begonnen werden. Bei A ist der aktuelle Rucksack leer (hat den Wert 0) und es ist ein Zugewinn von maximal 8\cdot 1.8 = 14.4 zu erwarten. Da 0+14.4 größer ist als der momentan beste Rucksack (ist zu Beginn ebenfalls leer, d.h. Wert gleich Null) muss A expandiert werden. Durch die Expandierung wird ein Rucksack gefunden der Gegenstand 1 enthält und somit den Wert 9 hat. Dieser wird nun zum momentan besten bekannten Rucksack und gibt mit seinem Wert eine erste Schranke vor. Als nächste Knoten kommen nun B und C in Frage. Bei B ist der aktuelle Rucksackwert 9 und durch den Zugewinn von 5 kann ein maximaler Rucksackwert von 14 erreicht werden. Bei C ist der maximal zu erreichende Wert nur 13.3. Aus diesem Grund sollte Knoten B bevorzugt behandelt werden. Knoten C wird für spätere eventuelle Expansionen "zur Seite gelegt". Folgende Tabelle zeigt die weitere Entwicklung:

Die Expandierung von B in Schritt 2 führt zu einem neuen besten Rucksack wodurch die Bound-Schranke auf 14 angehoben wird. In Schritt 3 kann für die verfügbaren Knoten C und E festgestellt werden, dass sich unterhalb keine bessere Lösung befinden kann.

Erst nachdem eine Rucksackbefüllung (1,1) mit 14 als Gesamtwert gefunden wurde, werden die Knoten C und E nicht mehr expandiert. Sie können nichts besseres als 13,3<14 liefern. Damit ergibt sich folgender dynamisch reduzierter Suchbaum bei dem weitere 6 Expandierung eingespart wurden.

Ausführliche Bearbeitung mit Boundbestimmung:

Implementation

Nur selten werden Branch and Bound Algorithmen rekursiv implementiert. Eine sortierte Queue (priority queue) ist zumeist die beste Option, um eine Menge abzuarbeitender Elemente zu verwalten, so wie es hier für die Knoten erforderlich ist. Die meisten höheren Programmiersprachen bieten hierzu entsprechende Datenstrukturen an. Hier wird heapq verwendet, um die zur Expandierung zur Verfügung stehenden Knoten nach ihrem maximal erreichbaren Rucksackwert sortiert bereitzustellen. Die Auswahl des als nächstes zu expandierenden Knotens kann so durch ein einfaches heappop realisiert werden.

Die Expandierung, also das Erzeugen neuer Knoten mit und ohne dem nächsten Gegenstand, erfolgt schlicht durch Anhängen von 1 oder 0 an die Liste welche einen Rucksack repräsentiert. Die expandierten Knoten werden nur dann der Queue hinzugefügt, wenn die Kapazitätsgrenze nicht überschritten wird und der maximal erreichbare Wert den momentan besten Rucksackwert überschreitet.

Gibt es keine zu prüfenden Knoten mehr, also wurden alle Knoten entweder bereits verarbeitet oder ausgeschlossen, steht das Endergebnis fest.

Traveling Salesman Problem (TSP)

Das oft zitierte Problem des Handlungsreisenden oder Rundreiseproblem besteht darin, eine vorgegebene Anzahl von Städten genau einmal zu besuchen und zum Ausgangspunkt zurückzukehren, wobei der zurückgelegte Gesamtweg minimal ist. Die Längen der Wegstrecken zwischen den Städten sind bekannt.

Dieses Problem haben aber nicht nur Handlungsreisende, sondern auch Logistikunternehmen (wie muss das Postauto fahren, sodass die Tour möglichst schnell geht), Platinen-Designer (wie müssen Kontakte verbunden werden, sodass möglichst wenig Edelmetall verbraucht wird) und viele mehr. In jedem Fall geht es darum, irgendwelche "Kosten" zu minimieren. Es handelt sich also um ein Optimierungsproblem.

Ein TSP lässt sich sehr einfach in Form von gewichteten Graphen darstellen, s. Abb. 2. Die die Städte repräsentierenden Knoten sind einfach durchnummeriert worden: 0,1,2,3, n=4. Die Gewichte der Kanten entsprechen hier den Kosten für den Übergang von einem Knoten zum anderen (z.B. dem Preis für eine Flugreise von Ort A nach Ort B). Die Kosten zwischen zwei Knoten können dabei auch von der Richtung abhängig sein.

Eine Entfernungsmatrix E, wie in Abb. 3, liefert auch eine adäquate Modellierung des gegebenen Sachverhalts. Die \infty-Einträge kennzeichnen unmögliche oder verbotene Übergänge.

Die Suche nach einem Weg mit minimalen Kosten kann auch hier mittels Entscheidungsbaum visualisiert werden: Die im Baumdiagramm (Abb. 4) jeweils eingetragenen Pfeile geben an, welche Stadt als nächste besucht wird. Da es sich um eine Rundreise handelt, spielt es keine Rolle, welcher Knoten die Wurzel des Baumes (Start und Ende der Rundreise) bildet.

Gibt es n Knoten, so gibt es im ersten Schritt n-1 Möglichkeiten die Reise fortzusetzen, im nächsten Schritt nur noch n-2 usw. bis nach n-2 Schritten nur ein Knoten als mögliches Ziel verbleibt. Mit der Rückkehr zum Ausgangspunkt schließt sich der Kreis und die Länge des Weges steht fest.

Der in Abb. 4 angegebene Baum protokolliert alle möglichen Städtebesuchsfolgen. Für die Suche der kürzesten Rundreise spielt es im Allgmeinen durchaus eine Rolle, auf welchem Weg die betrachtete Stadt erreicht wurde. Von daher brauchen wir für jeden Stadtbesuch im Protokoll (Abb. 4) eine aktualisierte Gesamtschau auf die noch möglichen Fortsetzungen des Weges.

Dies erreichen wir durch Modifikation der jeweils aktuellen Entfernungsmatrix und führen das am Beispiel 0\rightarrow 3 vor:

1. E[0,j]=\infty für j\neq 3: Besuche 3 von 0 aus, nicht von einer anderen Stadt her.
2. E[3,0]=\infty: Der Rückweg von 3 zu 0 ist verboten, da 0 bereits besucht wurde.
3. E[i,3]=\infty für i\neq 0: Nur von 0 besucht man 3, von keiner anderen Stadt aus.

Nach dem Übergang von 0 (Start/Ziel) zu 3 ergibt sich die in Abb. 5 angegebene modifizierte Entfernungsmatrix.

Das Verfahren zur Herstellung der (übergangsabhängigen) modifizierten Entfernungsmatrix lässt sich aus obigem Beispiel für a\rightarrow b verallgemeinern, indem wir 0 durch a und 3 durch b ersetzen.

1. E[a,j]=\infty für j\neq b: Besuche b von a aus, nicht von einer anderen Stadt her.
2. E[b,a]=\infty: Der Rückweg von b zu a ist verboten, da a bereits besucht wurde.
3. E[i,b]=\infty für i\neq a: Nur von a besucht man b, von keiner anderen Stadt aus.

Begrenzung und Ablauf

Um nun dafür zu sorgen, dass der jeweils vielversprechendste Knoten expandiert wird, benötigen wir eine Bewertungsfunktion. Diese soll für die (modifizierte) Entfernungsmatrix eines aktuellen Blattes des sich entwickelnden Baumes eine Schranke bestimmen. Im Falle des TSP muss dies eine untere Schranke für die Länge der kürzesten Rundreise, die auf diesem Weg erzielbar ist, sein. Für die Bewertungen zweier expandierbarer Knoten entscheidet man sich für den mit der besseren Bewertung, um die Expansion mit diesem fortzusetzen. Für diese Entscheidung werden alle aktuell expandierbaren Knoten herangezogen.

Bei der Suche einer geeigneten Bewertungsfunktion machen wir uns folgende Überlegung zunutze: Wenn man die gegebene Entfernungsmatrix E normiert, d.h. alle Zeileneinträge um das jeweilige Zeilenminimum verringert und anschließend alle Spalteneinträge um das jeweilige Spaltenminimum reduziert, ergibt sich eine Matrix \hat{E}. Dies entspricht der Idee, eine Stadt auf dem kürzesten Weg zu betreten und auf dem kürzesten Weg zu verlassen. Die kürzeste Rundreise für eine Städteanordnung mit \hat{E} hat mindestens die Länge 0. Diese Lösung (Städtefolge) stimmt mit der für E überein, nur dass die Rundreiselänge größer ist. Hieraus ergibt sich eine untere Schranke für die kürzeste Rundreise für E aus der Summe aller wie oben gebildeten Zeilen- und Spaltenminima. Abb. w illustriert das beschriebene Vorgehen der Matrixbewertung für den zunächst nur aus der Wurzel 0 bestehenden Baum in unserem Beispiel. Die kleinen Zahlen ergeben sich aus der Subtraktion des jeweiligen Zeilenminimums vom ursprünglichen Wert in dem betrachteten Feld von E. Die kleinen Zahlen verwendet man anschließend zur Bestimmung der Spaltenminima. Im Beispiel beträgt die untere Schranke 35.

Da es nur diesen Wurzelknoten gibt, kann nur dieser im nächsten Schritt expandiert werden. Entscheidet man sich für den Übergang zu Knoten 3, erhält man die in Abb. 5 angegebene Entfernungsmatrix, die man dem nun aktuellen Blatt zuordnet. Das zugehörige Bound beträgt wiederum 34, s. Abb. 7.

Die 34 bedeutet, dass es nicht möglich ist, auf diesem Weg eine kürzere Rundreise zu erzielen, als die der Länge 34. Die tatsächliche minimale Rundreise könnte also durchaus die Länge 40, jedoch nicht 30, haben.

Da der Knoten 0 durch mögliche Übergänge zu 1 und 2 und der Knoten 3 nach 0\rightarrow 3 weiterhin expansionsfähig sind, ist ein Bound-Vergleich erforderlich: Wegen 34<35 wird der Knoten 3 als nächster expandiert. Geschieht dies mit 3\rightarrow 1, ergibt sich ein Bound von 35. Wegen 34<35 wird wiederum Knoten 3 expandiert. Hierfür bleibt noch der Übergang 3\rightarrow 2, was allerdings zu einem Bound von 39 führt. Da es danach zwei Knoten, nämlich 0 und 0\rightarrow 3\rightarrow 1, mit einem Bound von 35 gibt, ist es gleichgültig, welchen Knoten man als nächstes expandiert. Entscheidet man sich für 0\rightarrow 3\rightarrow 1\rightarrow 2, ergibt sich wieder ein Bound von 35. Folglich ist es notwendig, die Wurzel des Baumes, also Knoten 0 zu expandieren. Sowohl für 0\rightarrow 1 als auch 0\rightarrow 2 erhalten wir 40, sodass wir keine Chance haben, einen kürzeren als den gefundenen Rundweg 0\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 0 mit einer Länge von 10+10+9+6=35 zu finden.

Es ist sehr wichtig, abschließend den Expansionsbaum zur Protokollierung des Ablaufs zu notieren, s. Abb. 8. Die jeweils expansionsfähigen Knoten dieses Baumes sind Wege, die von der Wurzel zu einem der betrachteten Knoten führen, nicht etwa die Knoten selbst. Als Repräsentation der Knoten des Baumes eignen sich die modifizierten Entfernungsmatrizen mit den zugehörigen Bounds.

Der in Abb. 8 dargestellte Baum wird durch Branch and Bound nicht vollständig aufgebaut. Die grau dargestellten Teile entfallen, da die Expansionen chancenlos wären. Durch diese Einsparung kann eine Effizienzverbesserung erzielt werden. Eine Verbesserung der Komplexitätsordnung ist nicht zu erwarten.

Alternative Lösungsraumstruktur: Der Entscheidungsbaum kann auch binär strukturiert werden, sodass man für jeden Knoten entscheidet, ob eine mögliche Kante dem Weg hinzugefügt (linker Ast) oder nicht aufgenommen (rechter Ast) wird. Es lohnt sich, auch diese Form zu bearbeiten.

Implementation

Die Entfernungsmatrix kann sehr einfach als zweidimensionales Array erstellt werden. Zur Repräsentation von Unendlich bieten die meisten höheren Programmiersprachen eine entsprechende Möglichkeit. Mit den Hilfsfunktionen >delta und >modify erfolgt die Berechnung der Schranke und die Anpassung der Entfernungsmatrix bei Festlegung eines Übergangs. Der eigentliche Algorithmus basiert auf einer Priority Queue die stets den erfolgversprechendsten Knoten zur Expandierung bereitstellt (mit unterer Schranke). Sobald ein Endpunkt erreicht ist (alle Knoten sind im Weg enthalten) ist die kürzeste Rundreise gefunden. Anderenfalls erfolgt die Expansion durch Modifizierung der Matrix und Berechnung der zugehörigen Schranke. Die Begrenzung erfolgt in diesem Fall indirekt durch Zurückstellung (nicht Löschung) der Expansion von Knoten mit einer hohen Schranke.