Branch and bound (metodo)

Il metodo dei rami e dei limiti (in inglese Branch and Bound, abbreviato B&B o BnB) è un paradigma generale per la costruzione di algoritmi esatti per la risoluzione di problemi di ottimizzazione discreta e combinatoria, in particolare di problemi NP-difficili. Il metodo rappresenta una strategia di enumerazione guidata, in cui l'intero insieme delle soluzioni ammissibili viene suddiviso sequenzialmente in sottoinsiemi (ramificazione), e per ciascuno di essi vengono calcolate stime (limiti) del valore della funzione obiettivo. Queste stime consentono di scartare (potare) quei sottoinsiemi che non possono certamente contenere soluzioni ottimali, riducendo in modo sostanziale lo spazio di ricerca.

Il metodo fu proposto per la prima volta da A. Land e A. Doig nel 1960 per la risoluzione di problemi di programmazione intera. Da allora è diventato uno degli approcci più fondamentali nella ricerca operativa e nell'informatica. La caratteristica chiave del metodo è la sua flessibilità: non si tratta di un algoritmo specifico, bensì di uno schema strategico di alto livello (framework), adattivo alla struttura del problema da risolvere.

Componenti chiave del metodo

Il metodo si basa su tre operazioni fondamentali, applicate ai sottoinsiemi dello spazio delle soluzioni, organizzati sotto forma di albero di ricerca.

• Ramificazione (in inglese Branching) — è il processo di suddivisione ricorsiva dell'insieme corrente di soluzioni ammissibili $S_i$ in diversi sottoinsiemi più piccoli, generalmente disgiunti $S_{i1},S_{i2},\dots ,S_{ik}$. Ciascun sottoinsieme corrisponde a un nuovo sottoproblema ed è rappresentato come nodo figlio nell'albero di ricerca. Ad esempio, nei problemi di programmazione intera la ramificazione viene spesso effettuata sulla variabile che assume un valore frazionario nella soluzione della rilassazione LP.

• Calcolo dei limiti (in inglese Bounding) — per ogni nodo dell'albero di ricerca (cioè per ogni sottoproblema) viene calcolata una stima del valore della funzione obiettivo. Per un problema di minimizzazione, questa è il limite inferiore (lower bound), che costituisce una stima garantita dal basso per qualsiasi soluzione del sottoinsieme dato. Nella maggior parte dei casi questa stima si ottiene risolvendo la rilassazione del sottoproblema originale — una versione semplificata in cui alcuni vincoli complessi (ad esempio, l'integrità) vengono temporaneamente ignorati. La più comune è la rilassazione LP.

• Potatura (in inglese Pruning) — è il processo di esclusione dalla considerazione di nodi (e dei sottoalberi a essi corrispondenti) che certamente non possono contenere la soluzione ottimale. Un nodo viene potato in uno dei seguenti casi:

1. Potatura per limite: Il limite inferiore per il nodo dato risulta non migliore (cioè maggiore o uguale, nel caso di minimizzazione) rispetto al valore della migliore soluzione ammissibile trovata fino a quel momento, denominata incumbent (incumbent).
2. Potatura per ammissibilità: La soluzione della rilassazione del nodo è ammissibile per il problema originale (ad esempio, tutte le variabili sono intere). Tale soluzione viene confrontata con l'incumbent corrente e, se è migliore, l'incumbent viene aggiornato. Non è necessaria alcuna ulteriore ramificazione da questo nodo.
3. Potatura per inammissibilità: Il sottoproblema corrispondente al nodo non ha soluzioni ammissibili.

Algoritmo generale

L'algoritmo generalizzato del metodo dei rami e dei limiti per un problema di minimizzazione può essere descritto nei seguenti passi:

1. Inizializzazione: Trovare una soluzione ammissibile iniziale (ad esempio, tramite un'euristica) e impostare il suo valore come limite superiore iniziale (incumbent) $U$. Creare la coda dei nodi attivi $Q$, contenente il nodo radice (il problema originale).
2. Ciclo principale: Finché la coda $Q$ non è vuota:
   • Selezionare un nodo da $Q$ in accordo con la strategia di ricerca (ad esempio, ricerca in profondità o per migliore stima).
   • Risolvere la rilassazione per questo nodo, ottenendo il limite inferiore $L$.
   • Potare il nodo se $L\ge U$.
   • Se la soluzione della rilassazione è ammissibile per il problema originale, aggiornare l'incumbent: $U\leftarrow L$.
   • Se il nodo non è stato potato e la soluzione non è ammissibile, eseguire la ramificazione, suddividendolo in nodi figli, e aggiungerli alla coda $Q$.
3. Terminazione: Quando la coda $Q$ diventa vuota, l'algoritmo termina. La soluzione trovata, corrispondente all'incumbent $U$, è globalmente ottimale.

Proprietà chiave e teoremi

• Correttezza e convergenza: L'algoritmo garantisce di trovare la soluzione globalmente ottimale in un numero finito di passi, a condizione che l'insieme delle soluzioni ammissibili sia finito e che la procedura di ramificazione sia convergente (ovvero che, nella suddivisione ricorsiva, i sottoinsiemi si «contraggano» verso dei punti).
• Strategia di ricerca: L'efficienza dell'algoritmo dipende fortemente dalla strategia di scelta del prossimo nodo da ramificare (ad esempio, ricerca in profondità, ricerca in ampiezza, ricerca per migliore stima) e dalla scelta della variabile di ramificazione. I moderni solver utilizzano spesso strategie ibride.

Esempi

• Problema di programmazione intera: Applicazione classica del metodo. Come rilassazione si utilizza la programmazione lineare. La ramificazione avviene sulla variabile frazionaria $x_j$, creando due sottoproblemi con vincoli aggiuntivi $x_j\le \lfloor x_j^{\ast }\rfloor$ e $x_j\ge \lceil x_j^{\ast }\rceil$.
• Problema del commesso viaggiatore: Lo spazio delle soluzioni è costituito da tutti i possibili cicli hamiltoniani nel grafo. La ramificazione può essere effettuata sugli archi (includere/escludere un arco dal percorso). Come limiti inferiori possono essere utilizzate le soluzioni di problemi più semplici, come il problema di assegnamento o la costruzione dell'albero di copertura minimo.

Concetti correlati e applicazioni

• Metodo dei rami e dei tagli (Branch-and-Cut): Metodo ibrido che combina B&B con il metodo dei piani di taglio. In ogni nodo dell'albero di ricerca, oltre alla soluzione della rilassazione, vengono generate disuguaglianze aggiuntive (tagli) che rafforzano il limite inferiore, portando a una potatura più efficiente dei rami.
• Ricerca con backtracking (Backtracking): Il metodo dei rami e dei limiti può essere considerato una generalizzazione di questo algoritmo per problemi di ottimizzazione.
• Potatura alfa-beta: Analogia concettuale utilizzata negli alberi di gioco per potare i rami sicuramente perdenti.

Vedi anche

• Programmazione intera
• Ottimizzazione combinatoria
• Problema del commesso viaggiatore
• Problema NP-difficile
• Metodo del simplesso

Note

</references>