Data un’istanza 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 .
Ciascun nodo figlio è ottenuto dal suo nodo padre aggiungendo alla formulazione matematica del problema corrispondente al nodo padre un vincolo di branching.
Supponiamo che stiamo valutando il sottoproblema corrispondente ad un generico nodo dell’albero di branching, risolvendo il suo rilassamento continuo corrispondente ad un’istanza di Problema dello Zaino Frazionario.
Può accedere che
non sia ammissibile: inutile investigare il sottalbero radicato in ;
abbia una soluzione ottima intera: inutile investigare il sottalbero radicato in , eventualmente si aggiornano e ;
non abbia una soluzione ottima intera , ma si è verificato il criterio di bounding: inutile investigare il sottalbero radicato in ;
non abbia una soluzione ottima intera e non si è verificato il criterio di bounding.
In questo ultimo caso, occorre investigare il sottalbero radicato in attraverso una operazione di branching che consiste nel generare e introducendo rispettivamente i vincoli di branching
dove è la componente critica frazionaria in .
Risolvere tramite algoritmo B&B la seguente istanza del Problema dello Zaino 0/1:
il cui rilassamento continuo è la seguente istanza del Problema dello Zaino Frazionario:
Inizializzare:
;
(stiamo risolvendo un problema di max).
Ordinando e rinumerando gli oggetti in ordine non crescente di profitto per unità di peso, si ha la seguente tabella:
La nuova formulazione matematica di coerente alla nuova numerazione è riportata di seguito:
Nell’individuare una soluzione ottima per si individua in 4 l’oggetto critico.
Infatti, risulta che
Dunque, la soluzione ottima per è data da
;
;
.
e il valore della funzione obiettivo corrispondente a è
Occorre effettuare un’operazione di branching, generando i sottoproblemi e :
Studiamo considerandone il rilassamento continuo , la cui soluzione ottima è calcolata applicando l’algoritmo greedy:
;
/* vincolo di branching */;
;
il valore della funzione obiettivo corrispondente a è
Non occorre investigare il sottalbero radicato nel nodo corrispondente a , perchè la soluzione ottima di ha tutte componenti intere.
Occorre aggiornare:
;
.
Studiamo considerandone il rilassamento continuo , la cui soluzione ottima è calcolata applicando l’algoritmo greedy:
;
/* vincolo di branching */;
;
;
il valore della funzione obiettivo corrispondente a è
Occorre investigare il sottalbero radicato nel nodo corrispondente a , perchè la soluzione ottima di non ha tutte componenti intere e non si è verificato il criterio di bounding.
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 è
cui corrisponde il valore ottimo di funzione obiettivo
1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
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.