Branch and bound

Da Wikipedia, l'enciclopedia libera.

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 in 1960 per risolvere problemi di programmazione lineare.

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à.

[modifica] Descrizione

Supponiamo di avere un problema $P 0 = (z, F (P 0))$ dove z è la funzione obiettivo del problema, mentre $F (P 0)$ è la regione ammissibile. La miglior soluzione ottima sarà $z^* = z(P^0) = \left \{ z(x) : x \in F(P^0) \right \}$ mentre $Z b e s t$ rappresenta la miglior soluzione ammissibile nota. Suddividiamo il problema $P 0$ in K sottoproblemi: $P 1, P 2,..., P K$ la cui totalità rappresenti $P 0$ , ad esempio si può suddividere $F (P 0)$ in K sottoinsiemi $F (P 1), F (P 2),..., F (P K)$ tali che:

$\bigcup_{i=1}^K F(P^i) = F(P^0)$

Preferibilmente le sottoregioni vanno partizionate in modo che:

$F(P^i) \cap F(P^j) = \varnothing \qquad \forall P^i,P^j : i \ne j$

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 $P 0$ è quindi equivalente a risolvere la totalità dei suoi $P K$ sottoproblemi generati:

$z^* = z(P^0) = \min \left \{z(P^1),z(P^2),...,z(P^K) \right \}$

Un sottoproblema $P i$ si considerare risolto se si verifica almeno uno dei seguenti casi:

Si determina la soluzione ottima di $P i$ ;
Si dimostra che $F (P i)$ è impossibile;
Si dimostra che $z(P^i) \ge z^{best}$ (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 $P i$ , è possibile determinare un lower bound della soluzione in modo da seguire una strategia di esplorazione dell'albero più efficiente.

$L(P^i) \le (P^i)$

Se verifico che $L(P^i) \ge z^{best}$ 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 $P i = (z, F (P 0))$ devo trovare un rilassamento del problema $R (P i) = (z r, F r (P i))$ tale che:

$F_r (P^i) \supseteq F(P^i)$ ;
$z_r (y) \le z(y) \qquad \forall y \in F(P^i)$ ;

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.

[modifica] Applicazioni

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.