Branch and Bound

Branch and bound (B&B) è il metodo esatto standard per la programmazione intera mista (MIP) e molti problemi di ottimizzazione discreta. Introdotto da Land e Doig (1960) per MIP, applicato al TSP da Little et al. (1963) e chiarito per i vincoli interi con la regola di branching di Dakin (1965). L'algoritmo partiziona ricorsivamente la regione ammissibile in sotto-regioni (branching — es. per variabile intera x con x* frazionario, due figli x ≤ ⌊x*⌋ e x ≥ ⌈x*⌉), risolve a ogni nodo una **rilassazione LP** per ottenere un bound inferiore (in minimizzazione), mantiene un bound superiore con la migliore soluzione intera ammissibile trovata (incumbent), **pota per bound** ogni nodo il cui bound LP non è migliore dell'incumbent, **pota per interezza** quando la soluzione LP è già intera, e scarta nodi non ammissibili. Quando l'albero è esaurito, l'incumbent è l'ottimo globale. Branch-and-cut (Padberg e Rinaldi 1991) accoppia B&B con piani di taglio ed è la spina dorsale dei solver MIP moderni. Branch-and-price (Barnhart et al. 1998) lo accoppia con generazione di colonne e risolve formulazioni enormi. Strategia di branching (most-fractional, strong branching, pseudocost branching), selezione dei nodi (best-first, depth-first, best-estimate) e presolving influenzano drasticamente la performance. Wolsey (1998) *Integer Programming* e Nemhauser e Wolsey (1988) sono riferimenti standard. I solver MIP moderni gestiscono problemi a 100M di variabili combinando B&B + tagli + euristiche.