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 Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 16.Ottimizzazione intera: il metodo Branch and Bound


Schema della lezione

In questa lezione si descrive il metodo Branch and Bound per l’ottimizzazione intera.

Si propongono esempi di problemi risolti con il metodo Branch and Bound: un problema di programmazione lineare con variabili intere e un problema con variabili intere binarie, il problema dello zaino, cioè del caricamento ottimo di un contenitore.

Il metodo Branch and Bound

Per la soluzione di problemi di programmazione intera di dimensioni reali non è praticabile un approccio di enumerazione totale o esplicita. Si rivela molto utile invece un approccio definito di “enumerazione parziale” o “implicita”. Esso è basato fondamentalmente sulla suddivisione di un problema in due o più sottoproblemi. Ciò significa che l’insieme delle soluzioni ammissibili viene partizionato in due o più sottoinsiemi la cui intersezione è nulla e la cui unione costituisce l’insieme di partenza. Si stabilisce quindi una corrispondenza tra sottoproblema e sottoinsieme di soluzioni. Ciascuno di questi sottoinsiemi può contenere la soluzione ottima del problema originario. Essi costituiscono quindi la lista dei sottoinsiemi “candidati”. In un generico stadio della procedura si individua con un opportuno criterio un sottoinsieme della lista e si calcola un limite per il valore di funzione obiettivo relativo alle soluzioni in esso contenute. Si sviluppa quindi un’analisi volta a decidere se il sottoinsieme in questione deve essere ulteriormente partizionato ed esaminato per determinare soluzioni ammissibili del problema, oppure può essere eliminato da ulteriori considerazioni.

Il metodo Branch and Bound

Quest’ultima condizione si può verificare in quattro casi:

  • è stata determinata la migliore soluzione ammissibile contenuta nel sottoinsieme, cioè viene determinata la soluzione ottima del sottoproblema ad esso corrispondente
  • si può provare che il sottoinsieme non può contenere soluzioni ammissibili
  • il valore limite della funzione obiettivo associato al sottoinsieme è peggiore (minore per un problema di max, maggiore per un problema di min) della migliore soluzione ammissibile fino a quel punto determinata per il problema originario
  • il sottoinsieme è dominato da un altro sottoinsieme già eliminato

Se si verifica una di queste quattro condizioni è inutile continuare ad esplorare il sottoinsieme e quindi lo si elimina. Se non si verifica nessuna di queste condizioni il sottoinsieme (sottoproblema) esaminato viene a sua volta partizionato in due o più sottoinsiemi (sottoproblemi), che vengono aggiunti alla lista degli insiemi (problemi) candidati, e si ripete la scelta di un insieme (problema) candidato da esplorare. La procedura si itera fino a quando non ci sono più sottoinsiemi (sottoproblemi) da esplorare. La migliore soluzione ammissibile trovata costituisce la soluzione ottima del problema originario.

Il metodo Branch and Bound

In ultima analisi le componenti fondamentali del metodo Branch and Bound, sono sostanzialmente quattro:

  • determinazione di un valore limite (bound) di funzione obiettivo per un generico insieme candidato (limite superiore per un problema di massimizzazione, limite inferiore per un problema di minimizzazione)
  • partizione di un insieme candidato e scelta della variabile di branching
  • determinazione del sottoinsieme candidato da esplorare
  • eliminazione degli insiemi candidati che non è più necessario esplorare

Questo approccio metodologico per la soluzione di problemi di ottimizzazione intera si definisce, con terminologia anglosassone, metodo Branch and Bound, perché basato su un meccanismo di partizione e ramificazione (branch) degli insiemi di soluzioni, e sul calcolo di un valore limite (bound) della funzione obiettivo.

Un problema di P.L. intera


Sottoinsiemi S1 e S2 esaminati dall’algoritmo


Sottoinsiemi S1 e S2 esaminati dall’algoritmo


Sottoinsiemi S11 e S22 esaminati dall’algoritmo


Sottoinsiemi S11 e S22 esaminati dall’algoritmo


La soluzione di S11 è soluzione del problema generale

(S_{11})\hspace{1cm}\text{Max  }z=2x_1+3x_2

s.a.

\begin{array}{rrrr}-1.3x_1+3x_2\leq 9\\3x_1+0.9x_2\leq 18\\ x_1\hspace{1,5cm}\leq 4\\x_2\leq 4\\ x_1,x_2\text{  interi}\end{array}

(S_{11})

x_1=4\hspace{2cm}x_2=4\hspace{2cm}z = 20

Il valore di z diventa il limite inferiore della f.o. del problema intero originario.

z = 20

LI = 20


Albero delle soluzioni generato dall’algoritmo Branch and Bound


Problema dello zaino (Knapsack problem)

E’ necessario caricare uno zaino che può sopportare un peso massimo b con prodotti di cui si conosce il valore ed il peso unitario. Determinare quali prodotti caricare, e in quali quantità, per massimizzare il valore caricato rispettando il vincolo di peso massimo.

Siano

  • p = ( p1,…, pn) il vettore dei pesi dei prodotti;
  • v = (v1,…, vn)  il vettore dei valori unitari dei prodotti;
  • n = (n1,…, nn)il vettore delle disponibilità;
  • b ≥ pj, j = 1, …, nil parametro di peso massimo b.

Sia x il vettore delle variabili xj ,  j = 1,…, n

Max z = ∑ j = 1, n vj xj
s.a

j = 1, n pj xj ≤ b

xj nj  j = 1,…, n

xj 0 intero j = 1,…, n

Problema dello zaino binario

Per ciascun prodotto è disponibile una sola unità.

E’ necessario utilizzare variabili binarie.

Il modello si semplifica

Max z = ∑ j = 1, n vj xj
s.a

j = 1, n pj xj ≤ b

 xj {0, 1}j = 1,…, n

Problema dello zaino – Un esempio

Il modello dello Zaino binario:

Max z = ∑ j = 1, n vj xj
s.a

j = 1, n pj xj ≤ b

xj {0, 1}j = 1,…, n

Il modello:

Max z = 32xA + 36xB +15xC +20xD + 5xE

s.a

16xA + 9xB + 5xC + 8xD + 5xE ≤ 32

xA, xB, xC, xD, xE = 0/1

Problema dello zaino – Un esempio


Problema dello zaino – Un esempio


Albero di ricerca best-first


Albero di ricerca depth-first


  • 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