Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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

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 ]}, \]
  • dove x^*_t è una soluzione soluzione ottima per \mbox{(Pli-c)}_t .

Problemi di PLI: Branch & Bound, 8

Problemi di PLI: Branch & Bound. Disegnato da Paola Festa

Problemi di PLI: Branch & Bound. Disegnato da Paola Festa


I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion