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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 15.Il Problema dello Zaino 0/1: un algoritmo B&B


Il Problema dello Zaino 0/1: un algoritmo B&B, 1

Data un’istanza \mbox{Z}_{0/1} del Problema dello Zaino 0/1, viene generata una successione gerarchica di sottoproblemi via via più “vincolati” e dunque più semplici da risolvere rappresentati graficamente attraverso l’albero di branching, il cui nodo radice è il nodo corrispondente al problema originario \mbox{Z}_{0/1} .

Ciascun nodo figlio è ottenuto dal suo nodo padre aggiungendo alla formulazione matematica del problema corrispondente al nodo padre un vincolo di branching.

Il Problema dello Zaino 0/1: un algoritmo B&B, 2

Supponiamo che stiamo valutando il sottoproblema \mbox{(Z$_{0/1}$)}_t corrispondente ad un generico nodo t dell’albero di branching, risolvendo il suo rilassamento continuo \mbox{(Z-c$_{0/1}$)}_t corrispondente ad un’istanza di Problema dello Zaino Frazionario.

Può accedere che
\mbox{(Z-c$_{0/1}$)}_t non sia ammissibile: inutile investigare il sottalbero radicato in t ;
\mbox{(Z-c$_{0/1}$)}_t abbia una soluzione ottima intera: inutile investigare il sottalbero radicato in t , eventualmente si aggiornano x_{\mbox{opt}} e z_{\mbox{opt}} ;
\mbox{(Z-c$_{0/1}$)}_t non abbia una soluzione ottima intera x^*_t , ma si è verificato il criterio di bounding: inutile investigare il sottalbero radicato in t ;
\mbox{(Z-c$_{0/1}$)}_t non abbia una soluzione ottima intera x^*_t e non si è verificato il criterio di bounding.

In questo ultimo caso, occorre investigare il sottalbero radicato in t attraverso una operazione di branching che consiste nel generare \mbox{(Z-c$_{0/1}$)}_{t+1} e \mbox{(Z-c$_{0/1}$)}_{t+2} introducendo rispettivamente i vincoli di branching
\[ x_h=0\qquad  \mbox{e}\qquad  x_h=1, \]
dove x_h è la componente critica frazionaria in x^*_t .

Un algortimo B&B per il Problema dello Zaino 0/1: esempio, 1

Risolvere tramite algoritmo B&B la seguente istanza del Problema dello Zaino 0/1:

\[  \begin{array}{lllll} \mbox{{\rm (Z$_{0/1}$)$_1$}} & \mbox{{\rm max}} & 32x_1+36x_2+15x_3+20x_4+5x_5 \\ & \mbox{{\rm s.a}} \\ & & 16x_1+9x_2+5x_3+8x_4+5x_5\leq 32 \\ & & x_j\in \{0,1\}, \ j=1,2,\ldots,5 \end{array} \]

il cui rilassamento continuo è la seguente istanza del Problema dello Zaino Frazionario:

\[ \begin{array}{lllll} \mbox{{\rm (Z-c$_{0/1}$)$_1$}} &\mbox{{\rm max}} & 32x_1+36x_2+15x_3+20x_4+5x_5\\&\mbox{{\rm s.a}}\\& & 16x_1+9x_2+5x_3+8x_4+5x_5\leq 32 \\ & & 0\leq x_j\leq 1, \ j=1,2,\ldots,5.\end{array} \]

Inizializzare:

x_{\mbox{opt}}:=\emptyset;
z_{\mbox{opt}}:=-\infty (stiamo risolvendo un problema di max).

Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 2

Ordinando e rinumerando gli oggetti in ordine non crescente di profitto per unità di peso, si ha la seguente tabella:

\begin{tabular}{|c|c|c|c|c|}\hline oggetto & peso &profitto&$\frac{p}{w}$\\\hline $1$ & $9$& $36$ & $4$\\\hline $2$ & $5$& $15$ & $3$\\\hline$3$ & $8$& $20$ & $2.5$\\\hline $4$ & $16$& $32$ & $2$\\ \hline$5$ & $5$& $5$ & $1$\\\hline \end{tabular}

La nuova formulazione matematica di \mbox{Z}_{0/1} coerente alla nuova numerazione è riportata di seguito:

\[\begin{array}{lllll} \mbox{{\rm (Z$_{0/1}$)$_1$}} & \mbox{{\rm max}} & 36x_1+15x_2+20x_3+32x_4+5x_5 \\ &\mbox{{\rm s.a}} \\ & & 9x_1+5x_2+8x_3+16x_4+5x_5\leq 32 \\ & & x_j\in \{0,1\}, \ j=1,2,\ldots,5. \end{array} \]

Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 3

Nell’individuare una soluzione ottima per \mbox{(Z-c$_{0/1}$)}_1 si individua in 4 l’oggetto critico.
Infatti, risulta che
\[ \displaystyle{\sum_{j=1}^{3}w_j}=9+5+8=22<\displaystyle{\sum_{j=1}^{4}w_j}=9+5+8+16=38. \]

Dunque, la soluzione ottima x^{1*} per \mbox{(Z-c$_{0/1}$)}_1 è data da

x^{1*}_1=x^{1*}_2=x^{1*}_3=1 ;

x^{1*}_4=\frac{W-\displaystyle{\sum_{j=1}^{3}w_j}}{w_4}=\frac{32-22}{16}=\frac{5}{8} ;

x^{1*}_5=0 .

e il valore della funzione obiettivo corrispondente a x^{1*} è

\[ z(x^{1*})=32\cdot \frac{5}{8}+36+15+20=91. \]

Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 4

Occorre effettuare un’operazione di branching, generando i sottoproblemi \mbox{(Z$_{0/1}$)}_2 e \mbox{(Z$_{0/1}$)}_3:

\[\begin{array}{lllll} \mbox{{\rm (Z$_{0/1}$)$_2$}} & \mbox{{\rm max}} & 36x_1+15x_2+20x_3+32x_4+5x_5 \\ & \mbox{{\rm s.a}} \\ & & 9x_1+5x_2+8x_3+16x_4+5x_5\leq 32 \\ & & x_4=0 \\ & & x_j\in \{0,1\}, \ j=1,2,\ldots,5. \end{array} \] \[\begin{array}{lllll} \mbox{{\rm (Z$_{0/1}$)$_3$}} & \mbox{{\rm max}} &36x_1+15x_2+20x_3+32x_4+5x_5 \\ & \mbox{{\rm s.a}} \\ & & 9x_1+5x_2+8x_3+16x_4+5x_5\leq 32 \\ & & x_4=1 \\ & & x_j\in \{0,1\}, \ j=1,2,\ldots,5. \end{array} \]

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

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


Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 5

Studiamo \mbox{(Z$_{0/1}$)}_2 considerandone il rilassamento continuo \mbox{(Z-c$_{0/1}$)}_2, la cui soluzione ottima x^{2*} è calcolata applicando l’algoritmo greedy:

x^{2*}_1=x^{2*}_2=x^{2*}_3=1 ;

x^{2*}_4=0 /* vincolo di branching */;

x^{2*}_5=1 ;

il valore della funzione obiettivo corrispondente a x^{2*} è
\[ z(x^{2*})=36+15+20+5=76. \]

Non occorre investigare il sottalbero radicato nel nodo corrispondente a \mbox{(Z$_{0/1}$)}_2, perchè la soluzione ottima di \mbox{(Z-c$_{0/1}$)}_2 ha tutte componenti intere.
Occorre aggiornare:
x_{\mbox{opt}}:=x^{2*}=(1\ 1\ 1\ 0\ 1) ;
z_{\mbox{opt}}:=76 .

Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 6

Studiamo \mbox{(Z$_{0/1}$)}_3 considerandone il rilassamento continuo \mbox{(Z-c$_{0/1}$)}_3, la cui soluzione ottima x^{3*} è calcolata applicando l’algoritmo greedy:

x^{3*}_1=x^{3*}_2=1 ;
x^{3*}_4=1 /* vincolo di branching */;
x^{3*}_3=\frac{W-(w_1+w_2+w_4)}{w_3}=\frac{32-30}{8}=\frac{1}{4} ;
x^{3*}_5=0 ;

il valore della funzione obiettivo corrispondente a x^{3*} è
\[z(x^{3*})=36+15+\frac{1}{4}\cdot 20+32=88. \]

Occorre investigare il sottalbero radicato nel nodo corrispondente a \mbox{(Z$_{0/1}$)}_3, perchè la soluzione ottima di \mbox{(Z-c$_{0/1}$)}_3 non ha tutte componenti intere e non si è verificato il criterio di bounding.

Secondo livello dell’albero di branching. Disegnato da Paola Festa

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


Un algoritmo B&B per il Problema dello Zaino 0/1: esempio, 7

Procedendo come finora mostrato, viene generato l’albero di branching riportato in Figura.

L’algoritmo termina quando non ci sono sottoproblemi ancora da analizzare o, in termini di albero di branching, quando non ci sono sottalberi ancora da esplorare.

La soluzione ottima del problema originario \mbox{(Z$_{0/1}$)}_1 è

\[ x_{\mbox{opt}}:=x^{6*}=(1\ 1\ 0\ 1\ 0), \]

cui corrisponde il valore ottimo di funzione obiettivo \[ z_{\mbox{opt}}=83.\]

Albero di branching. Disegnato da Paola Festa

Albero di branching. 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