Branch and bound
Il branch and bound è una tecnica generale per la risoluzione di problemi di ottimizzazione combinatoria (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere.
Questo metodo è stato inizialmente proposto da A. H. Land e A. G. Doig nel 1960 per risolvere problemi di programmazione lineare intera.
Gli algoritmi Branch and Bound sono detti di enumerazione implicita perché si comportano esattamente come un algoritmo di enumerazione -cioè "provano" tutte le soluzioni possibili fino a trovare quella ottima (o quella corretta)- ma ne scartano alcune dimostrando a priori la loro non ottimalità.
Descrizione[1][modifica | modifica wikitesto]
Supponiamo di avere un problema dove z è la funzione obiettivo del problema, mentre è la regione ammissibile. La miglior soluzione ottima sarà mentre rappresenta la miglior soluzione ammissibile nota. Suddividiamo il problema in K sottoproblemi: la cui totalità rappresenti , ad esempio si può suddividere in K sottoinsiemi tali che:
Preferibilmente le sottoregioni vanno partizionate in modo che:
Questo processo di ramificazione (branching) si può rappresentare mediante un albero decisionale (branch decision tree), dove ogni nodo rappresenta il sottoproblema mentre ogni arco la relazione di discendenza.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c8/Branch_and_Bound.png/400px-Branch_and_Bound.png)
Risolvere il problema è quindi equivalente a risolvere la totalità dei suoi sottoproblemi generati:
Un sottoproblema si può considerare risolto se si verifica almeno uno dei seguenti casi:
- Si determina la soluzione ottima di ;
- Si dimostra che è vuota (cioè è inammissibile);
- Si dimostra che (la soluzione del sottoproblema è peggiore della migliore conosciuta).
Se non riesco a risolvere un nodo lo devo suddividere in altri sottoproblemi. Inoltre per ogni sottoproblema , è possibile determinare un lower bound della soluzione in modo da seguire una strategia di esplorazione dell'albero più efficiente.
Se verifico che posso escludere quel nodo visto che la miglior soluzione che posso sperare di ottenere è peggiore della soluzione ammissibile del problema originale. Per ottenere un lower bound di devo trovare un rilassamento del problema tale che:
- ;
- ;
Il problema rilassato è risolvibile in modo più semplice rispetto al problema originale, quindi posso trovarne la soluzione ottima che rappresenta il lower bound del problema originale. Il rilassamento inoltre deve essere scelto in modo che sia più vicino possibile (tight) al problema originale, in alcuni casi basta un rilassamento continuo (facilmente risolvibile attraverso l'algoritmo del simplesso), in altri casi può essere conveniente utilizzare altri rilassamenti come il rilassamento surrogato o il rilassamento lagrangiano.
Esempio[modifica | modifica wikitesto]
L'obiettivo è trovare la soluzione ottima intera per il problema dello zaino assegnato:
Poiché ogni variabile ha un costo ed un peso , il primo passo da compiere è ordinare le variabili secondo il criterio: .
In questo caso le variabili sono già ordinate poiché , quindi posso procedere alla determinazione di una soluzione ottima intera corrente a cui corrisponde un valore ottimo della funzione obiettivo.
Una possibile soluzione ottima intera è a cui corrisponde un valore ottimo della funzione obiettivo .
Sotto queste ipotesi, il vincolo viene rispettato ma non è del tutto ottimizzato, infatti ottengo la disequazione . Devono quindi essere cercate le soluzioni tali che il vincolo di capacità possa essere saturato.
Viene posto quindi , ovvero che corrisponde al valore ottimo . La soluzione però non è intera, quindi genero due sottoproblemi in corrispondenza della componente non intera, cioè :
che corrisponde all'ottimo (migliore dell'ottimo precedente). In questo caso, poiché il valore ottimo risulta migliore e la soluzione è intera, posso chiudere ed aggiornare la soluzione e l'ottimo corrente rispettivamente con i valori di e appena trovati.
che corrisponde all'ottimo (peggiore dell'ottimo precedente). Poiché la soluzione è intera ma , posso chiudere senza aggiornare nessun parametro.
Non avendo altri sottoproblemi aperti, la soluzione ottima intera ed il valore ottimo della funzione obiettivo risultano rispettivamente e .
Applicazioni[modifica | modifica wikitesto]
Questo approccio è stato usato per alcuni problemi NP-hard, per esempio
- Problema dello zaino
- Programmazione intera
- Programmazione non-lineare
- Problema del commesso viaggiatore (TSP)
Può essere utilizzato anche come base per vari algoritmi euristici. Per esempio, è possibile fermare il branching quando la differenza fra la soluzione trovata e il lower bound diventa inferiore rispetto ad una certa soglia. Questo è utile quando la soluzione trovata è "buona abbastanza" per i nostri scopi con il vantaggio di ridurre notevolmente il tempo di calcolo.
Note[modifica | modifica wikitesto]
- ^ S. Martello, "Algoritmi branch-and-bound: strategie di esplorazione e rilassamenti", in Metodi di Ottimizzazione per le Decisioni (a cura di G. Di Pillo), Milano, Masson, 1994.