I metodi Branch-and-bound sono algoritmi che risolvono un problema di ottimizzazione limitando o ramificando successivamente le variabili decisionali. Nel processo viene costruito un cosiddetto albero decisionale. Prima di ogni nuova ramificazione in un nodo, si verifica se il sottoalbero sotto questo nodo può essere presente in una soluzione ottimale. A tal fine, viene risolto un problema di ottimizzazione più semplice (rilassamento), che specifica un limite per la migliore soluzione possibile in questo sottoalbero.
Un metodo branch-and-bound consiste quindi in un processo alternato di ramificazione e calcolo dei limiti. Un buon metodo branch-and-bound è caratterizzato dal fatto che il rilassamento può essere risolto rapidamente, il rilassamento fornisce un valore vicino alla soluzione ottimale del problema originale e, in media, è necessario generare il minor numero possibile di nodi nell'albero decisionale.
I metodi branch-and-bound sono i cosiddetti “algoritmi esatti”. Ciò significa che forniscono sempre una soluzione ottimale se il tempo di calcolo è sufficientemente lungo. Sfortunatamente, il tempo di calcolo necessario per ottenere la soluzione esatta aumenta esponenzialmente con il tempo di esecuzione, per cui in pratica solo alcune classi di problemi di ottimizzazione possono essere risolte con questi metodi.
Nella pianificazione degli itinerari, in singoli casi si utilizzano i cosiddetti metodi “branch-and-price” o “branch-and-cut” o una loro combinazione (“branch-and-price-and-cut”). Questi metodi possono risolvere bene alcuni tipi di problemi (di grandi dimensioni) (ad esempio, i problemi dei venditori ambulanti).
