Branch-and-Bound

Vorgehensweise

Bound, die Schranke

Der Bound-Schritt hat die Aufgabe, bestimmte Zweige des Baumes "abzuschneiden", d. h. in der weiteren Berechnung nicht mehr zu betrachten, um so den Rechenaufwand zu begrenzen. Dies erreicht der Algorithmus durch Berechnung und Vergleich zweier Schranken. Obere Schranken ergeben sich aus jeder zulässigen Lösung. Dafür kann gegebenenfalls zuvor eine Heuristik benutzt werden.

Um gute untere Schranken (Bound) zu finden, wird oft eine Relaxation zugrunde gelegt. Das ist eine auf einer Menge definierte, leicht zu berechnende Funktion g mit für alle . Das relaxierte Problem bei sei leicht lösbar undbesitze eine Optimallösung x. Dann gilt offensichtlich für alle . Bei ist xauch Optimallösung des nicht relaxierten Problems.

Diese Überlegungen sind auch auf Teilprobleme anwendbar, wo also die MengeD bereits aufgespalten wurde. Kennt man bereits eine zulässigeLösung und ist die untere Schranke für einTeilproblem größer als , dann braucht man jenesTeilproblem nicht weiter zu untersuchen, weil es keine Optimallösung ergibt.