Branch & Bound e Branch & Cut per problemi di Programmazione Lineare Intera.

L'impiego della strategia di esplorazione best-bound first impone che il primo problema da investigare sia quello a cui e associato il bound più promettente. Una volta calcolato il bound del problema originario (Pli), si generano tutti i suoi figli e si ricavano i corrispondenti lower bound: il nodo da esplorare e quello a cui corrisponde il lower bound minore5; si determinano dunque tutti i suoi sottoproblemi, e i relativi bound.

A questo punto, il prossimo sottoproblema da investigare, tra tutti i problemi generati e non risolti, e nuovamente quello a cui corrisponde il lower bound piu basso; qualora, durante lo svolgimento, sia trovata una soluzione ottima intera, eventualmente vengono aggiornate le variabili xopt e zopt, e conseguentemente non verranno contemplati nell'elenco dei problemi da risolvere quelli a cui e associato un bound peggiore di zopt.

Utilizzando una strategia che ogni volta seleziona il sottoproblema da risolvere in relazione al bound ad esso associato, si ottiene il vantaggio di produrre con molta probabilita una soluzione ammissibile con un buon valore di funzione obiettivo; tuttavia, i sottoproblemi generati, trovandosi in livelli poco profondi del branching tree, sono poco vincolati: infatti, prima che si ottengano soluzioni ammissibili, è necessario esplorare un numero elevato di nodi.

Inoltre, la mancanza di una relazione tra due problemi analizzati consecutivamente e il gran numero di sottoproblemi contemporaneamente non risolti, comportano una maggiore difficoltà nell'implementazione dell'algoritmo e una gran quantità di memoria utilizzata, nonché un aumento del tempo impiegato per l'investigazione di ciascun sottoproblema.