Direkt zum Inhalt

Lexikon der Mathematik: branch-and-bound

Methode zur Lösung bestimmter Optimierungsprobleme.

Die Methode des branch-and-bound beruht auf dem Prinzip, ein großes Problem aufzuteilen in verschiedene Unterprobleme (Zweige = branches), und das in bestimmter Hinsicht günstigste dieser Unterprobleme zur weiteren Verarbeitung auszuwählen. Dazu ist es nötig, jeden Zweig bewerten zu können, um festzustellen, welcher der zur Auswahl stehenden Zweige der aktuell günstigste ist. Man schätzt dabei im allgemeinen eine Schranke (bound) für die Zielfunktion ab, sodaß man ein Maß für die Güte des aktuellen Zweiges erhält. Das Verfahren führt zu einem Baum, an dem man sowohl die einzelnen Unterprobleme als auch die optimale Lösung ablesen kann. Das Verfahren des branch-and-bound wird auch als Verzweigungsverfahren bezeichnet.

Eine Standardanwendung für branch-and-bound ist das sogenannte Problem des Handlungsreisenden. Man betrachtet dabei einen Handlungsreisenden, der in einer bestimmten Stadt eine Rundreise startet, die ihn durch n − 1 weitere Städte und zum Schluß wieder in die erste Stadt führt. In jeder Stadt will er genau einmal Station machen. Zu bestimmen ist die Reihenfolge der n − 1 anzulaufenden Städte mit dem Ziel, die zurückgelegte Distanz oder aber die Reisekosten oder ähnliches minimal zu halten. Bezeichnet man mit cij die Kosten von der i-ten zur j-ten Station, so kann man das Problem präziser mit Hilfe der Matrix

\begin{eqnarray}C=({C}_{11} & {c}_{12} & \cdots & {c}_{1n}\\ {C}_{21} & {c}_{22} & \cdots & {c}_{2n}\\ \vdots & \vdots & & \vdots \\ {C}_{m1} & {c}_{m2} & \cdots & {c}_{mn})\end{eqnarray}

formulieren. Gesucht ist nämlich eine Permutation (i1, …, in) von (1, …, n), so daß \({c}_{{i}_{1},{i}_{2}}+{c}_{{i}_{2},{i}_{3}}+\cdots +{c}_{{i}_{n-1},{i}_{n}}+{c}_{{i}_{n},{i}_{1}}\) minimal wird. Die einfachste Möglichkeit, alle Wege durchzutesten und so den Weg mit dem minimalen Aufwand zu finden, führt zu einer Komplexität von n!, die im allgemeinen nicht akzeptabel ist. Daher kommt hier der branch-and-bound-Ansatz zum Tragen. Man definiert als Kostenabschätzung die Mindestkosten eines Problems P durch

\begin{eqnarray}M(P)=\displaystyle \sum _{i=1}^{n}(\mathop{\min }\limits_{j\ne i}{c}_{ij}+\mathop{\min }\limits_{j\ne i}{c}_{ij})/2,\end{eqnarray}

wobei durch zwei dividiert wird, weil ansonsten jede Kante doppelt gezählt wird. Anhand dieser Mindestkosten beurteilt man dann die verschiedenen Unterprobleme. Hat man beispielsweise das folgende konkrete Problem:

\begin{eqnarray}{P}_{1}=(\infty & 3 & 2 & 7\\ 4 & \infty & 3 & 6\\ 1 & 1 & \infty & 3\\ 1 & 6 & 6 & \infty ),\end{eqnarray}

bei dem die Strecken von Station i nach Station i mit Unendlich bewertet werden, um sie von vornherein auszuschließen, so findet man die Mindestkosten \(M({P}_{1})=\frac{1}{2}(3+4+3+4)=7\). Nun kann man mit Station 1 beginnen und annehmen, daß von dort nach Station 3 gefahren wird. Das zugehörige Teilproblem P11 läßt sich wieder mit einer Matrix darstellen und hat die Mindestkosten M(P11) = 7, 5. Die Alternative P12, daß man zwar in Station 1 startet, aber nicht nach Station 3 fährt, hat Mindestkosten von M(P12) = 8. Folglich wird zunächst der Zweig P11 weiterverfolgt. Auf diese Weise erhält man insgesamt den folgenden Baum von Unterproblemen, der schließlich zu den zwei möglichen optimalen Wegen Station 1 – Station 2 – Station 3 – Station 4 bzw. Station 1 – Station 3 – Station 2 – Station 4 führt. Allgemein führt der branch-and- bound-Ansatz beim Problem des Handlungsreisenden zu einer Komplexität von 2n, was eine deutliche Verbesserung gegenüber n! darstellt.

Abbildung 1 zum Lexikonartikel Brandt, Heinrich Karl Theodor
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Teilproblembaum für das Problem des Handlungsreisenden

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos