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 S₁ e S₂ esaminati dall’algoritmo

Sottoinsiemi S₁ e S₂ esaminati dall’algoritmo

Sottoinsiemi S₁₁ e S₂₂ esaminati dall’algoritmo

Sottoinsiemi S₁₁ e S₂₂ esaminati dall’algoritmo

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 = ( p₁,…, p_n) il vettore dei pesi dei prodotti;
• v = (v₁,…, v_n)  il vettore dei valori unitari dei prodotti;
• n = (n₁,…, n_n)il vettore delle disponibilità;
• b ≥ p_j, j = 1, …, nil parametro di peso massimo b.

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

Max z = ∑ _{j = 1, n} v_j x_j
s.a

∑ _{j = 1, n} p_j x_j ≤ b

x_j ≤ n_j  j = 1,…, n

x_j ≤ 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} v_j x_j
s.a

∑ _{j = 1, n} p_j x_j ≤ b

 x_j ≤ {0, 1}j = 1,…, n

Problema dello zaino – Un esempio

Il modello dello Zaino binario:

Max z = ∑ _{j = 1, n} v_j x_j
s.a

∑ _{j = 1, n} p_j x_j ≤ b

x_j ≤ {0, 1}j = 1,…, n

Il modello:

Max z = 32x_A + 36x_B +15x_C +20x_D + 5x_E

s.a

16x_A + 9x_B + 5x_C + 8x_D + 5x_E ≤ 32

x_A, x_B, x_C, x_D, x_E = 0/1

Problema dello zaino – Un esempio

Problema dello zaino – Un esempio

Albero di ricerca best-first

Albero di ricerca depth-first