Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschränkung bzw. Verzweigung (branching) von Entscheidungsvariablen lösen. Dabei wird ein sogenannter Entscheidungsbaum (decision tree) aufgebaut. Vor jeder neuen Verzweigung in einem Knoten wird geprüft, ob der Teilbaum, der unter diesem Knoten liegt, überhaupt in einer optimalen Lösung vorkommen kann. Dazu wird ein einfacher zu lösendes Optimierungsproblem gelöst (Relaxation), welches eine Schranke (bound) für die bestmögliche Lösung in diesem Teilbaum angibt.
Daher besteht ein Branch-and-Bound-Verfahren in einem abwechselnden Prozess der Verzweigung und Berechnung von Schranken. Ein gutes Branch-and-Bound-Verfahren ist dadurch gekennzeichnet, dass die Lösung der Relaxation schnell erfolgen kann, die Relaxation einen Wert nahe an der optimalen Lösung des ursprünglichen Problems liefert und im Mittel möglichst wenig Knoten im Entscheidungsbaum erzeugt werden müssen.
Branch-and-Bound-Verfahren sind sogenannte „exakte Algorithmen“. Das heißt, dass sie bei genügend langer Rechenzeit immer eine optimale Lösung liefern. Leider steigt die dafür notwendige Rechenzeit in der Regel exponentiell mit der Laufzeit, sodass in der Praxis nur wenige Klassen von Optimierungsproblemen mit diesen Verfahren gelöst werden können.
In der Tourenplanung kommen in einzelnen Fällen sog. Branch-and-Price-Verfahren oder Branch-and-Cut-Verfahren bzw. Kombinationen davon („Branch-and-Price-and-Cut“) zum Einsatz. Diese können bestimmte Typen von (großen) Problemen (z. B. Travelling-Salesman-Probleme) gut lösen.
