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

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.

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:

  1. Si determina la soluzione ottima di  ;
  2. Si dimostra che   è vuota (cioè  è inammissibile);
  3. 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:

  1.  ;
  2.  ;

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.

EsempioModifica

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  .

ApplicazioniModifica

Questo approccio è stato usato per alcuni problemi NP-hard, per esempio

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.

NoteModifica

  1. ^ 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.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica