Home

Federica EU

1/8

Paola Festa » 13.Problemi di PLI: Branch & Bound

Problemi di PLI: Branch & Bound, 1

La matrice dei coefficienti tecnologici $A$ di un problema di Programmazione Lineare Intera (Pli) non è in generale unimodulare, per cui la soluzione ottima del suo rilassamento continuo (Pli-c) ha una o più componenti frazionarie.

Un algoritmo che può essere applicato per individuare una soluzione ottima per un problema di Programmazione Lineare Intera (Pli) è noto come Branch & Bound (B&B).

Si tratta di una tecnica enumerativa implicita che affronta un problema di PLI suddividendolo in due sottoproblemi sempre di PLI, ma più semplici, in quanto di taglia inferiore.

Problemi di PLI: Branch & Bound, 2

Si consideri un problema di PLI (Pli), la cui regione ammissibile è rappresentata in Figura. La soluzione ottima del rilassamento continuo è $x^*=\left(\frac{3}{2},\ 2\right)$ . E’ chiaro che la soluzione ottima intera avrà $x_1\leq 1$ oppure $x_2\geq 2$ . Allora, si procede aggiungendo il solo vincolo $x_1\leq 1$ alla formulazione originaria di (Pli) così ottenendo il problema $\mbox{(Pli)}_{x_1\leq 1}$ , che ha soluzione ottima $x^*_{x_1\leq 1}$ . Successivamente, si aggiunge la sola condizione $x_1\geq 2$ alla formulazione originaria di (Pli) così ottenendo il problema $\mbox{(Pli)}_{x_1\geq 2}$ , che ha soluzione ottima $x^*_{x_1\geq 2}$ . A questo punto, è immediato individuare la soluzione ottima intera al problema (Pli), scegliendo fra le soluzioni $x^*_{x_1\leq 1}$ e $x^*_{x_1\geq 2}$ quella cui corrisponde un migliore valore della funzione obiettivo.

Regione ammissibile X del problema di PLI. Disegnata da Paola Festa

Problemi di PLI: Branch & Bound, 3

In generale, dato il seguente problema di PLI

$\begin{array}{lllll}\mbox{{\rm (Pli$_1$)}} & \mbox{{\rm min}} & z(x)& =& c'x \\& \mbox{{\rm s.a}} \\ & & Ax & =& b \\ & & \ \ x& \geq& 0\ \mbox{{\rm ed intero}},\end{array}$

si risolve il suo rilassamento continuo

$\begin{array}{lllll} \mbox{{\rm (Pli-c)$_1$}} & \mbox{{\rm min}} & z(x)& =& c'x \\ & \mbox{{\rm s.a}} \\ & & Ax & =& b \\ & & \ \ x& \geq& 0. \end{array}$

Sia $x^*$ una soluzione ottima per (Pli-c). Se $x^*$ ha tutte componenti intere, allora $x^*$ è una soluzione ottima anche per (Pli).

Problemi di PLI: Branch & Bound, 4

Altrimenti, (vedi Figura) si sceglie una componente $x^*_h$ frazionaria e si costruiscono i seguenti due sottoproblemi:

$\begin{array}{lllll} \mbox{{\rm (Pli)$_2$}} & \mbox{{\rm min}} & z(x)& =& c'x \\ & \mbox{{\rm s.a}} \\ & & Ax & = & b \\ & & x_h & \leq& \lfloor x^*_h\rfloor \\ & &\ \ x&\geq& 0\ \mbox{{\rm ed intero}}, \end{array} \] \[\begin{array}{lllll} \mbox{{\rm (Pli)$_3$}} & \mbox{{\rm min}} & z(x)& =& c'x \\ & \mbox{{\rm s.a}} \\ & & Ax & =& b \\ & & x_h & \geq& \lceil x^*_h\rceil \\ & &\ \ x&\geq& 0\ \mbox{{\rm ed intero}}. \end{array}$

Primo livello dell'albero di branching. Disegnato da Paola Festa

Problemi di PLI: Branch & Bound, 5

L’operazione di costruzione dei sottoploblemi $\mbox{(Pli)}_2$ e $\mbox{(Pli)}_3$ a partire da $\mbox{(Pli)}_1$ si chiama operazione di branching (ramificazione), mentre $x_h$ è detta variabile di branching. $\mbox{(Pli)}_2$ e $\mbox{(Pli)}_3$ si dicono figli di (Pli), a partire dal quale sono ottenuti aggiungendo alla formulazione matematica di (Pli) rispettivamente i vincoli di branching

$x_h\leq\lfloor x^*_h\rfloor\qquad \mbox{e}\qquad x_h\geq\lceil x^*_h\rceil.$

$\mbox{(Pli)}_2$ e $\mbox{(Pli)}_3$ sono problemi della “stessa natura” di $\mbox{(Pli)}_1$ , per cui per risolverli si applica lo stesso procedimento, ossia per ciascuno dei sottoproblemi si risolve all’ottimo il corrispondente rilassamento continuo e, se necessario, si effettua a partire da essi un ulteriore operazione di branching. Si ottiene così procedendo una successione gerarchica di sottoproblemi via via più “vincolati” e dunque più semplici da risolvere rappresentati graficamente attraverso il cosiddetto albero di branching, il cui nodo radice è il nodo corrispondente al problema originario (Pli). Ciascun nodo figlio è ottenuto dal suo nodo padre aggiungendo alla formulazione matematica del problema corrispondente al nodo padre un vincolo di branching.

Problemi di PLI: Branch & Bound, 6

In generale, i vincoli di un problema $\mbox{(Pli)}_t$ associato ad un nodo $t$ dell’albero di branchingsono:

i vincoli del problema originario ( $Ax=b,\ x\geq 0\ \mbox{e intero}$ );
tutti i vincoli di branching che si incontrano lungo il cammino dal nodo radice al nodo $t$ (il nodo $t$ “eredita” i vincoli dei suoi antenati).

In linea di principio, l’albero di branching può contenere tutte le combinazioni possibili di branching e, cioè, enumerare tutte le soluzioni intere e fra queste scegliere quella cui corrisponde il miglior valore della funzione obiettivo. Tuttavia, come vedremo fra breve, potrebbe non essere necessario considerare esplicitamente tutti i nodi potenzialmente presenti nell’albero.

Problemi di PLI: Branch & Bound, 7

Supponiamo che stiamo valutando il sottoproblema $\mbox{(Pli)}_t$ corrispondente ad un generico nodo $t$ dell’albero di branching e sia $x_{\mbox{opt}}$ la migliore soluzione intera finora trovata cui corrisponde un valore della funzione obiettivo pari a $z_{\mbox{opt}}$ .

E’ inutile operare un branching a partire da $t$ se si verifica una delle seguenti condizioni.

Il rilassamento continuo $\mbox{(Pli-c)}_t$ non è ammissibile. Ciò accade quando $\mbox{(Pli-c)}_t$ ha una regione ammissibile vuota e cioè quando i vincoli originari sono incompatibili con i vincoli di branching che si incontrano lungo il cammino dalla radice al nodo $t$ .
Il rilassamento continuo $\mbox{(Pli-c)}_t$ ha una soluzione ottima intera. In tal caso, eventualmente si aggiornano $x_{\mbox{opt}}$ e $z_{\mbox{opt}}$ .
Il rilassamento continuo $\mbox{(Pli-c)}_t$ non ha una soluzione ottima intera, ma si è verificato il criterio di bounding: $c'x^*_t \geq z_{\mbox{opt}}\ \mbox{[ N.B. $c'x^*_t \leq z_{\mbox{opt}}$, se (Pli) \`e un problema di massimo ]},$