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

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)=\{z(x):x\in F(P^0)\}$ mentre $z^{best}$ 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 \mathrm{\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 \{z(P^1),z(P^2),...,z(P^K)\}$

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

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

1. $F_r(P^i)\supseteq F(P^i)$;
2. $z_r(y)\le z(y)\mathrm{\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.

Esempio

L'obiettivo è trovare la soluzione ottima intera per il problema dello zaino assegnato:

$\{\begin{array}{c}\max 6x_1+3x_2+4x_3+2x_4+x_5\\ 2x_1+x_2+2x_3+x_4+x_5\le 4\\ x\in \{0,1\}\end{array}$

Poiché ogni variabile ha un costo $c_i$ ed un peso $a_i$, il primo passo da compiere è ordinare le variabili secondo il criterio: $\frac{c_1}{a_1}\ge \frac{c_2}{a_2}\ge ...\ge \frac{c_n}{a_n}$.

In questo caso le variabili sono già ordinate poiché $\frac{6}{2}\ge \frac{3}{1}\ge \frac{4}{2}\ge \frac{2}{1}\ge \frac{1}{1}$ , quindi posso procedere alla determinazione di una soluzione ottima intera corrente a cui corrisponde un valore ottimo della funzione obiettivo.

Una possibile soluzione $x^{*}$ ottima intera è $x^{*}=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\end{array}\right]$ a cui corrisponde un valore ottimo della funzione obiettivo $z^{*}=6$.

Sotto queste ipotesi, il vincolo viene rispettato ma non è del tutto ottimizzato, infatti ottengo la disequazione $2x_1+x_2+2x_3+x_4+x_5\le 4⟶2\le 4$. Devono quindi essere cercate le soluzioni tali che il vincolo di capacità possa essere saturato.

Viene posto quindi $x_1=1,x_2=1,x_3=\frac{1}{2},x_4=0,x_5=0$ , ovvero $x^{*}=\left[\begin{array}{c}1\\ 1\\ \frac{1}{2}\\ 0\\ 0\end{array}\right]$ che corrisponde al valore ottimo $z^{*}=11$. La soluzione $x^{*}$ però non è intera, quindi genero due sottoproblemi in corrispondenza della componente non intera, cioè $x_3$:

$P_1){\overline{x}}_3=\lfloor x_3\rfloor =\lfloor \frac{1}{2}\rfloor ⟶{\overline{x}}_3=0$

${\overline{x}}_3=0⟶x^{(1)}=\left[\begin{array}{c}1\\ 1\\ 0\\ 1\\ 0\end{array}\right]$ che corrisponde all'ottimo $z^{(1)}=11$ (migliore dell'ottimo precedente). In questo caso, poiché il valore ottimo risulta migliore e la soluzione è intera, posso chiudere $P_1$ ed aggiornare la soluzione $x^{*}$ e l'ottimo corrente $z^{*}$ rispettivamente con i valori di $x^{(1)}$ e $z^{(1)}$ appena trovati.

$P_2){\overline{x}}_3=\lceil x_3\rceil =\lceil \frac{1}{2}\rceil ⟶{\overline{x}}_3=1$

${\overline{x}}_3=1⟶x^{(2)}=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\\ 0\end{array}\right]$ che corrisponde all'ottimo $z^{(2)}=10$ (peggiore dell'ottimo precedente). Poiché la soluzione $x^{(2)}$ è intera ma $z^{(2)}<z^{*}$, posso chiudere $P_2$ senza aggiornare nessun parametro.

Non avendo altri sottoproblemi aperti, la soluzione ottima intera ed il valore ottimo della funzione obiettivo risultano rispettivamente $x^{*}=\left[\begin{array}{c}1\\ 1\\ 0\\ 1\\ 0\end{array}\right]$ e $z^{*}=11$.

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.