Branch and Bound

Branch and Bound (B&B) ist das exakte Standardlösungsverfahren für gemischt-ganzzahlige Programmierung (MIP) und viele diskrete Optimierungsprobleme. Es wurde von Land und Doig (1960) für MIP eingeführt, von Little et al. (1963) auf TSP angewandt und mit der Verzweigungsregel von Dakin (1965) für ganzzahlige Restriktionen geklärt. Der Algorithmus zerlegt den zulässigen Bereich rekursiv in Teilbereiche (Verzweigen — z. B. für ganzzahlige Variable x mit fraktionalem x* zwei Kinder x ≤ ⌊x*⌋ und x ≥ ⌈x*⌉), löst an jedem Knoten eine **LP-Relaxation**, um eine untere Schranke (bei Minimierung) zu erhalten, hält über die beste gefundene ganzzahlig-zulässige Lösung (Incumbent) eine obere Schranke, **schneidet per Schranke** jeden Knoten, dessen LP-Schranke nicht besser als das Incumbent ist, **schneidet per Ganzzahligkeit**, wenn die LP-Lösung bereits ganzzahlig ist, und verwirft unzulässige Knoten. Ist der Baum erschöpft, ist das Incumbent das globale Optimum. Branch-and-Cut (Padberg und Rinaldi 1991) verbindet B&B mit Schnittebenen und ist das Rückgrat moderner MIP-Solver. Branch-and-Price (Barnhart et al. 1998) kombiniert es mit Column Generation und löst riesige Formulierungen. Verzweigungsstrategie (most-fractional, strong branching, pseudocost branching), Knotenauswahl (best-first, depth-first, best-estimate) und Presolving beeinflussen die B&B-Leistung dramatisch. Wolsey (1998) *Integer Programming* und Nemhauser und Wolsey (1988) sind Standardreferenzen. Moderne MIP-Solver bewältigen 100M-Variable-Probleme durch die Kombination von B&B + Schnitten + Heuristiken.