Skip to content
Torna ai risultati

Branch and Bound

Introdotto da
Ailsa Land & Alison Doig
Anno
1960
Tipo
Exact combinatorial optimization algorithm
Famiglia
Mathematical programming

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Il Branch and Bound è un algoritmo esatto sistematico per problemi di ottimizzazione combinatoria e intera, introdotto da Ailsa Land e Alison Doig nel 1960.

Organizza lo spazio di ricerca come un albero di sottoproblemi, utilizza limiti superiori derivati da rilassamenti per potare i rami che non possono migliorare la migliore soluzione nota e garantisce il ritrovamento di una soluzione intera globalmente ottimale. È la spina dorsale dei moderni risolutori di programmazione a interi misti utilizzati nella ricerca operativa, nella logistica, nella pianificazione e nella progettazione ingegneristica.

L’intuizione alla base del metodo

Immaginate di cercare l'oggetto di maggior valore nascosto in un vasto labirinto di stanze. Invece di controllare ogni stanza, stimate il massimo valore possibile raggiungibile da ogni corridoio prima di entrarvi. Se questo "soffitto" è inferiore al miglior oggetto che già possedete, saltate l'intero corridoio senza guardarci dentro. Il Branch and Bound funziona allo stesso modo: divide il problema in pezzi più piccoli, calcola limiti superiori ottimistici per ogni pezzo e scarta immediatamente qualsiasi pezzo che provatamente non possa superare la soluzione corrente migliore.

Storia

Land e Doig pubblicarono il fondamentale articolo sul Branch and Bound in Econometrica nel 1960, inquadrandolo come un metodo automatico per la programmazione discreta. Little et al. (1963) applicarono la tecnica al problema del commesso viaggiatore, consolidandone il ruolo nell'ottimizzazione combinatoria. Dakin (1965) introdusse il branching con rilassamento LP, la forma più comunemente usata oggi. I decenni successivi videro l'integrazione di piani di taglio (branch-and-cut) e generazione di colonne (branch-and-price), rendendo il Branch and Bound il motore di tutti i principali risolutori commerciali di programmazione intera.

Quando usarlo

Utilizzate il Branch and Bound quando dovete trovare la soluzione provatamente ottimale per un programma lineare a interi misti o puri e non potete accettare una risposta approssimata. Presuppone che il problema possa essere formulato con rilassamenti lineari (o convessi) che forniscano limiti utili. È meno adatto per istanze molto grandi in cui l'albero di enumerazione esplode, per programmi a interi non lineari senza rilassamenti stretti, o per contesti in tempo reale in cui il tempo di calcolo è strettamente limitato. In tali casi, si possono preferire euristiche o metaeuristiche.

Limiti e considerazioni

  • La complessità nel caso peggiore è esponenziale; su istanze mal strutturate l'albero può crescere in modo proibitivo.
  • Le prestazioni sono altamente sensibili alla scelta della variabile di branching e alla strategia di selezione dei nodi.
  • Richiede un rilassamento trattabile che fornisca limiti superiori significativi; limiti deboli portano a una potatura minima.
  • I requisiti di memoria possono essere sostanziali quando molti nodi aperti devono essere memorizzati simultaneamente.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Garantisce l'ottimalità globale per programmi interi e combinatori.
  • Riduce drasticamente la ricerca tramite la potatura basata sui limiti — spesso viene esplorata solo una piccolissima frazione dell'intero albero di enumerazione.
  • Flessibile: può incorporare piani di taglio (branch-and-cut) o limiti euristici (branch-and-price) per un'ulteriore efficienza.
  • Ampiamente implementato in risolutori commerciali maturi (CPLEX, Gurobi) e strumenti open-source (GLPK, CBC).

Applicazioni

  • Pianificazione degli equipaggi aerei e assegnazione della flotta nella ricerca operativa.
  • Progettazione di reti di supply-chain e problemi di localizzazione di impianti.
  • Layout di circuiti VLSI e allocazione di registri nell'ingegneria informatica.
  • Previsione della struttura proteica e assemblaggio del genoma nella biologia computazionale.
  • Ottimizzazione del portafoglio finanziario con vincoli di cardinalità.

Come funziona

Come funziona

1

L'algoritmo inizia risolvendo una versione rilassata del problema — tipicamente il rilassamento LP — che ignora i vincoli di integralità. Questo rilassamento fornisce un limite superiore al vero valore ottimale perché ogni soluzione intera ammissibile è anche ammissibile nel rilassamento. Se la soluzione rilassata risulta essere a valori interi, il problema è risolto immediatamente.

Formula
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

Quando la soluzione rilassata contiene una variabile frazionaria, l'algoritmo partiziona la regione ammissibile aggiungendo vincoli complementari che forzano la variabile al suo floor o al suo ceiling. Ogni partizione crea un nuovo nodo figlio nell'albero di ricerca, suddividendo efficacemente un sottoproblema in due sottoproblemi più piccoli con domini più ristretti.

Formula
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Ogni nodo attivo riceve il proprio limite di rilassamento LP. Un nodo il cui limite non supera la migliore soluzione intera trovata finora — chiamata incumbent — non può contenere una soluzione migliore, quindi viene potato. Limiti stretti sono critici: più il limite è stretto, meno nodi devono essere esplorati.

Formula
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Un nodo viene "fathomed" (chiuso permanentemente) in tre condizioni: il suo rilassamento è inammissibile, il suo limite non è migliore dell'incumbent, o la sua soluzione rilassata è già intera-ammissibile. In quest'ultimo caso, l'incumbent viene aggiornato se la nuova soluzione lo migliora. L'algoritmo termina quando tutti i nodi sono "fathomed", a quel punto l'incumbent è l'ottimo globale.

Formula
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Errori comuni

  • Scegliere male la variabile di branching (ad esempio, ramificando sempre sulla prima variabile frazionaria) porta spesso ad alberi profondi e sbilanciati e a una lenta convergenza.
  • Ignorare le disuguaglianze valide (piani di taglio) significa perdere l'opportunità di stringere significativamente i limiti di rilassamento.
  • La terminazione prematura con un gap di subottimalità che non viene segnalato come tale può indurre in errore i professionisti a trattare una soluzione quasi ottimale come esatta.
  • L'applicazione del Branch and Bound a rilassamenti non lineari o non convessi senza una convessificazione specializzata può produrre limiti non validi e risultati errati.

Domande frequenti

In che modo il Branch and Bound differisce dall'enumerazione esaustiva?

L'enumerazione esaustiva valuta esplicitamente ogni soluzione intera ammissibile, il che è computazionalmente infattibile per problemi di grandi dimensioni. Il Branch and Bound evita ciò calcolando limiti superiori basati su rilassamenti a ogni nodo dell'albero di ricerca e potando interi sottoalberi ogni volta che il limite non può superare la migliore soluzione già trovata. In pratica, solo una piccola frazione dell'albero viene mai esaminata.

Qual è il ruolo del rilassamento LP nel Branch and Bound?

Il rilassamento LP elimina i vincoli di integralità, rendendo il problema risolvibile in tempo polinomiale con il metodo del simplesso o del punto interno. Il suo valore ottimale funge da limite superiore per il corrispondente sottoproblema intero. Quando questo limite è stretto — vicino all'ottimo intero vero — meno rami devono essere esplorati. Rilassamenti più stretti, spesso ottenuti aggiungendo disuguaglianze valide, accelerano drasticamente l'algoritmo complessivo.

Quando dovrei usare il Branch and Bound rispetto a una metaeuristica come gli algoritmi genetici?

Scegliete il Branch and Bound quando richiedete un certificato di ottimalità e potete permettervi il tempo di calcolo. È ideale per problemi di medie dimensioni con rilassamenti LP ben strutturati. Le metaeuristiche sono preferibili quando il problema è estremamente grande, manca di un rilassamento utile, o deve essere risolto entro un budget di tempo ristretto in cui una soluzione quasi ottimale è accettabile. Molti professionisti combinano entrambi: usano il Branch and Bound con una tolleranza di gap per la terminazione anticipata.

Metodi correlati

Fonti

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    Apri il riferimento DOI
    Copiato.