Lexikon der Mathematik: Verzweigungsverfahren
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}
(mit \(A\in {{\mathbb{R}}}^{m\times n},b\in {{\mathbb{R}}}^{m},c\in {{\mathbb{R}}}^{n}\)). Als erstes Teilproblem untersuchen wir das lineare Programm\begin{eqnarray}(L{P}_{0}):min\,{c}^{T}\cdot x\end{eqnarray}
unter den Nebenbedingungen\begin{eqnarray}A\cdot x=b,x\ge 0,\end{eqnarray}
\begin{eqnarray}{c}^{T}\cdot {x}^{0}=:{z}^{0}.\end{eqnarray}
Sollte x0 bereits ganzzahlig sein, so ist das Problem gelöst. Andernfalls beginnt die Verzweigung: Wir wählen eine Komponente \({x}_{j}^{0}\) in x0, die nicht in ℕ0 liegt. Daraufhin konstruieren wir, ausgehend von (LP0), zwei neue Probleme (LP1) und (LP2), und zwar einmal, indem wir zu (LP0) die Nebenbedingung\begin{eqnarray}{x}_{j}\le \lfloor {x}_{j}^{0}\rfloor \end{eqnarray}
hinzufügen, das andere Mal, indem wir\begin{eqnarray}{x}_{j}\ge \lfloor {x}_{j}^{0}\rfloor \end{eqnarray}
\begin{eqnarray}\min \{{z}_{1},{z}_{2}\}={z}_{0},\end{eqnarray}
d. h. z0 ist eine untere Schranke für den Optimalwert der beiden Teilprobleme.Die Probleme (LPi), 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}
so kann man den Teilbaum mit Wurzel v löschen: Keines der zu seinen Knoten gehörenden Probleme kann noch einen besseren als den schon für z* berechneten Wert liefern. Dies liegt an der bereits beschriebenen Beziehung zwischen den Optimalwerten von Problemen auf demselben Pfad im Baum. Auf diese Art läßt sich im Idealfall eine vollständige Suche im gesamten Verzweigungsbaum vermeiden und der Aufwand eines Lösungsverfahrens signifikant verringern.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.
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.