Mit Branch and Bound ("Verzweige und begrenze") werden Strategien bezeichnet, bei denen man während der Expansion des Lösungsgraphen eine Bewertung der jeweiligen Teillösungen durchführt mit dem Ziel, Teiläste des Lösungsgraphen auszuschließen und dadurch den Umfang der weiteren Suche zu beschränken.
Bortfeldt (s.76) gibt in seinem Buch ein schönes Beispiel zu Maschinenbelegungsplänen an.
Es ist lohnend, den Weg der Expansion des Entscheidungsgraphen zu verfolgen. Die Anmerkungen geben Hilfe.
Wie wir aber beim Hierarchischen Generate and Test gesehen haben, löst dies nicht allein das Problem, da der Aufwand immer noch sehr hoch sein kann.