Il branch and bound è un metodo generale per risolvere problemi di programmazione intera. Combina due idee:
- branch: dividere il problema in sottoproblemi aggiungendo vincoli;
- bound: usare limiti superiori o inferiori per eliminare sottoproblemi che non possono migliorare la soluzione nota.
L’algoritmo esplora un albero di ricerca. Ogni nodo rappresenta un problema rilassato, spesso ottenuto togliendo il vincolo di interezza. Se il problema originale è di minimizzazione, la rilassazione fornisce un bound inferiore; se è di massimizzazione, fornisce un bound superiore. La migliore soluzione intera già trovata è detta incumbent.
Se la rilassazione lineare produce una variabile frazionaria:
si generano due rami:
Un nodo viene potato quando:
| Caso | Motivo della potatura |
|---|---|
| inammissibile | non contiene soluzioni valide |
| soluzione intera | aggiorna l’incumbent o chiude il nodo |
| bound sfavorevole | non può battere la migliore soluzione nota |
La qualità della formulazione è decisiva. Vincoli Big-M troppo grandi, variabili ridondanti e rilassazioni deboli producono molti nodi e tempi di calcolo elevati. Una formulazione più stretta può ridurre drasticamente l’albero di ricerca anche se ha più vincoli.
Nelle implementazioni moderne il branch and bound è spesso integrato con piani di taglio, euristiche primal, preprocessing, probing e strategie di scelta del nodo. In quel caso si parla di branch and cut o branch and price, ma l’idea di fondo resta la stessa: esplorare solo le parti dell’albero che possono contenere una soluzione migliore.
Un errore comune è immaginare il metodo come una enumerazione cieca di tutte le combinazioni. La forza del branch and bound sta proprio nella potatura: se i bound sono buoni, gran parte delle combinazioni non viene mai esplorata.
Vedi anche: Programmazione intera, Programmazione lineare, Ricerca operativa, Ottimizzazione.