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 c_ij 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}

\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}

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