allgemeines Konzept zum Entwurf von Algorithmen zur Lösung zahlreicher Probleme in Mathematik und Informatik.

Verzweigungsverfahren zählen zu den kombinatorischen Methoden, da bei ihrem Entwurf kombinatorische Fragestellungen eine wesentliche Rolle spielen. Wir stellen das grundlegende Prinzip von Verzweigungsverfahren (auch „divide et impera” bzw. „branch and bound”) anhand der ganzzahligen linearen Optimierung dar.

Ausgangspunkt von Verzweigungsverfahren ist die Idee, einem gegebenen Problem eine Menge von Teilproblemen zuzuordnen. Startend mit einem solchen Problem werden iterativ weitere Teilprobleme erzeugt, sodaß insgesamt eine Baumstruktur von Problemen entsteht. Diese Zerlegung hat so zu geschehen, daß eine vollständige Lösung aller Teilprobleme die nötige Information auch über die Lösung des Ausgangsproblems liefert.

Dies gelingt theoretisch durch ein vollständiges Durchsuchen des Baums. Gerade das soll aber bei Verzweigungsverfahren vermieden werden. An dieser Stelle tritt der zweite Aspekt, nämlich das Beschränken (bound bzw. herrsche) in Kraft. Dabei versucht man, für jedes Teilproblem Schranken für mögliche Lösungen des Gesamtproblems zu finden. Die gefundenen Schranken ermöglichen es im Idealfall, daß man die Probleme in gewissen anderen Teilbäumen nicht mehr weiter untersuchen muß und somit den Suchraum verkleinert.

Wir betrachten als Beispiel ein rein ganzzahliges lineares Optimierungsproblem

\begin{eqnarray}\min {c}^{T}\cdot x\end{eqnarray}

\begin{eqnarray}A\cdot x=b,x\ge 0,x\in {{\mathbb{Z}}}^{n}\end{eqnarray}

\begin{eqnarray}(L{P}_{0}):min\,{c}^{T}\cdot x\end{eqnarray}

\begin{eqnarray}A\cdot x=b,x\ge 0,\end{eqnarray}

\begin{eqnarray}{c}^{T}\cdot {x}^{0}=:{z}^{0}.\end{eqnarray}

\begin{eqnarray}{x}_{j}\le \lfloor {x}_{j}^{0}\rfloor \end{eqnarray}

\begin{eqnarray}{x}_{j}\ge \lfloor {x}_{j}^{0}\rfloor \end{eqnarray}

\begin{eqnarray}\min \{{z}_{1},{z}_{2}\}={z}_{0},\end{eqnarray}

Die Probleme (LP_i), i = 1, 2, werden anschließend analog weiter zerlegt, indem man eine Komponente ihrer Lösung, welche nicht ganzzahlig ist, auswählt und entsprechende Nebenbedingungen zufügt. Wir erhalten so einen binären Baum, dessen Knoten je einem Teilproblem entsprechen. Bei genügend häufiger Verzweigung liefern die Probleme an den Blättern ganzzahlige Lösungen (man beachte, daß das Hinzufügen der Nebenbedingungen schließlich ganzzahlige Ecken bei der entsprechenden Zulässigkeitsmenge erzeugt). Die Beziehung zwischen den Optimalwerten aller Probleme in einem Teilbaum und dem Optimalwert des Problems an der Wurzel desselben gilt unverändert: Dieser ist eine untere Schranke für jene.

An dieser Stelle kommt die Idee des Beschränkens ins Spiel: Angenommen, man hat eine ganzzahlige Lösung z* für eines der Teilprobleme (etwa an einem Blatt des Verzweigungsbaums) berechnet. Weiter angenommen, man hat für ein anderes Teilproblem, das zu irgendeinem Knoten v des Verzweigungsbaums gehört, eine Lösung \(\tilde{z}\) berechnet, die nicht ausschließlich ganzzahlig sein muß. Ist jetzt

\begin{eqnarray}{c}^{T}\cdot \tilde{z}\ge {c}^{T}\cdot {z}^{\ast},\end{eqnarray}

Natürlich vernachlässigt die obige Darstellung einige wichtige Aspekte bei der Umsetzung derartiger Verfahren, wie etwa geeignete Suchstrategien, um im Baum zulässige Lösungen zu finden, die es dann erlauben, möglichst viele Teile des Baums zu vernachlässigen. Als Beispiel eines solchen Problems ist beim Verzweigen die Auswahl einer Komponente, die nicht ganzzahlig ist, zu nennen.

Ausführliche Darstellungen zugehöriger Techniken finden sich in den meisten Büchern über kombinatorische Optimierung, zum Beispiel in [1]

[1] K.G. Murty: Linear and Combinatorial Programming. John Wiley and Sons, 1976.