Il problema dello zaino: dalla gita in montagna ai trasporti

Il problema dello zaino: dalla gita in
montagna ai trasporti internazionali
Luca Bertazzi
0
Il problema dello zaino
Zaino:
- capacità B
Oggetti (items):
- numero n
- indice i = 1,2,..., n
- valore pi
wi
- peso
Quali oggetti inserire nello zaino al fine di
massimizzare il valore totale?
Applicazioni classiche
Gita in montagna
Sbarco sulla luna
Applicazioni finanziarie
B.
Un investitore ha un capitale
p
Può sottoscrivere progetti di investimento.
O i progetto i :
Ogni
- richiede un capitale wi
- ha un rendimento pi
Quali progetti sottoscrivere al fine di massimizzare
ill rendimento
d
totale?
l
Applicazioni alla Logistica
1) Gestione della produzione
Un produttore ha a disposizione una
barra di ferro di una data lunghezza B.
La barra può essere tagliata in pezzi.
Ogni pezzo i :
-ha
ha una lunghezza wi
-ha un prezzo di vendita pi
Quali pezzi tagliare al fine di massimizzare il ricavo
totale?
2) Gestione magazzini e scorte
Area di ricezione
Area di stoccaggio remoto
Area ad accesso rapido
A
Area
di spedizione
di i
Area ad accesso rapido
- Dimensione dell’area: B
- Ogni prodotto:
- occupa un volume wi
- implica un time saving pi
se collocato nell’area
Quali prodotti collocare
nell’area
nell
area per massimizzare
il time saving totale?
3) Gestione dei trasporti
Trasporti nell’e-business
Un veicolo di capacità B ,
durante il viaggio di ritorno,
può
ò scegliere
li
di servire
i
alcuni clienti.
Ogni cliente:
- occupa
p un volume wi
- fornisce un profitto pi
Quali clienti servire per
massimizzare il profitto totale?
Backhauling
kh l
Trasporti internazionali
Un gestore di cargo ha a
disposizione un aereo merci
di capacità
i à B.
Ha una lista di carichi
carichi. Ogni
carico:
- occupa
p un volume wi
- fornisce un profitto pi
Quali carichi scegliere al fine di massimizzare
il profitto totale?
4) Logistica integrata
1
0
3
Strategie di
produzione e
spedizione che
ottimizzino:
• Produzione
• Trasporto
• Scorte
sistemi integrati di produzione e distribuzione
Problema dello zaino: soluzioni intuitive
Algoritmo pi - greedy
- Ordinare gli oggetti
sulla base di pi in
modo non crescente
B = 15
n=5
i
pi
wi
4Î1Î2Î5Î3
1
2
3
4
5
4
2
1
10
2
12
2
1
4
1
- Inserire gli oggetti
fino al raggiungimento
della capacità
4
z
pi −greedy
greedy
= 10
Esiste una soluzione migliore?
B = 15
n=5
i
pi
wi
1
2
3
4
5
4
2
1
10
2
12
2
1
4
1
Se inseriamo nello
zaino gli oggetti
2-3-4-5 otteniamo:
Profitto totale: 15
Peso totale:
8
Î Esiste!!
Conclusione:
L’algoritmo pi-greedy non è esatto (non assicura
di ottenere una soluzione ottima)
Qual è il limite di questo algoritmo?
Non tener conto del peso degli oggetti
e quindi del profitto per unità di peso
Un secondo algoritmo
Profitto per
unità di peso
B = 15
n=5
i
pi
wi
pi / wi
1
2
3
4
5
4
2
1
10
2
12
2
1
4
1
00,33
33
1
1
2,5
2
Algoritmo Greedy
- Ordinare gli oggetti
sulla base di pi / wi in
modo non crescente
4Î5Î2Î3Î1
- Inserire gli oggetti
fino al raggiungimento
gg
g
della capacità
4Î 5 Î 2 Î 3
z Greedy = 15
L’algoritmo Greedy è esatto?
Greedy:
B = 200
n=3
1Î2
i
pi
wi
pi / wi
1
2
3
2
100
100
1
100
100
2
1
1
z Greedy = 102
Altra soluzione:
inserire 2 e 3
Profitto totale: 200
• Profitto totale del Greedy: 102
• Esiste una soluzione con p
profitto 200
Î Il profitto ottimo è almeno 200
Conclusione:
•L
L’algoritmo
algoritmo Greedy non è esatto
• Esiste almeno un caso in cui il profitto del
Greedy è il 51% del profitto ottimo
E’ il caso peggiore?
Greedy:
B = 200
n=2
1
i
pi
wi
pi / wi
1
2
2
200
1
200
2
1
z Greedy = 2
Altra soluzione:
inserire 2
Profitto totale: 200
L’algoritmo Greedy può generare soluzioni
con profitto
fitt molto
lt basso
b
rispetto
i
tt all’ottimo
ll’ tti
Esiste un algoritmo
g
con p
profitto minimo
garantito?
L’algoritmo Ext-Greedy
Scegliere la migliore fra:
- la soluzione del Greedy
- la soluzione che contiene solo l’oggetto
con profitto
fitt massimo
i
L’algoritmo
’ l
Ext-Greedy
d genera un
profitto pari ad almeno il 50% del
profitto
f
ottimo
Alla ricerca della soluzione ottima
Come determinare una soluzione ottima?
Algoritmo di completa enumerazione
- Generare tutte le soluzioni
- Scegliere la soluzione ammissibile con il
p ofitto maggiore
profitto
maggio e
B = 200
n=3
i
pi
wi
1
2
3
2
100
100
1
100
100
1
SI
2
3 profitto peso
NO NO 2
1
SI
SI
SI
NO
NO
NO
NO
NO
SI
SI
N0
NO
SI
SI
SI
NO
SI
NO
SI
NO
SI
102
102
202
0
100
100
200
101
101
201
0
100
100
200
3 oggetti Î 8 soluzioni
L’algoritmo di completa enumerazione genera
sempre una soluzione ottima
ottima, ma…
ma
Numero di soluzioni:
n oggetti
2n soluzioni
oggetti
numero di soluzioni
3
8
60
1.152.921.500.000.000.000
90
1.23794 E 27
Come varia il tempo di calcolo al variare di n?
n
Tempo di calcolo
3
< 1 secondo
d
60
19 ore
90
392 secoli
un milione
ili
di miliardi
ili di di operazioni
i i all secondo
d
ÎL
L’algoritmo
algoritmo di completa enumerazione
può essere impraticabile
Non solo brutte notizie…
Èp
possibile ottenere la soluzione ottima di
problemi con migliaia di oggetti in
pochi secondi su un PC
p
n
5000
15000
25000
t
tempo
15 sec
1 min
1 min e 25 sec
Come è possibile
ottenere questo
risultato?
Solver: CoinMP 1.3
PC: AMD Athlon 64 X2 Dual Core Processor 5600+ 3.4 GB RAM
Ricerca operativa
metodi quantitativi e scientifici nei
processi decisionali
O
Operations
ti
Research:
R
h
The Science of Better
Ricerca operativa
Applicazioni:
Logistica
Fi
Finanza
Telecomunicazioni
Data Mining
Bio-informatica
Gestione delle Risorse Umane
Gestione dei Servizi Sanitari
…
What-if?
What-is-best?
Metodo:
PROBLEMA
MODELLO
ALGORITMI
software
1) Definizione del problema
PROBLEMA
MODELLO
Quali oggetti inserire
nello zaino al fine di
massimizzare il profitto
totale?
ALGORITMI
software
Dati:
B : capacità
p
dello zaino
n : numero di oggetti
pi : profitto dell
dell'oggetto i
wi : peso dell'oggetto i
2) Formulazione di un modello
1) Variabili decisionali:
L’oggetto
gg
i viene inserito
nello zaino?
PROBLEMA
MODELLO
Variabile binaria xi ∈ {0,1}
xi
0 Î i non viene
i
inserito
1 Î i viene inserito
ALGORITMI
software
2) Funzione obiettivo:
PROBLEMA
massimizzare il profitto totale
0 se xi = 0
MODELLO
Profitto oggetto i
pi se xi = 1
Profitto totale:
n
∑ p i xi
i =1
ALGORITMI
software
Funzione obiettivo:
PROBLEMA
massimizzare il profitto totale
MODELLO
n
max ∑ pi xi
i =1
i=1
ALGORITMI
software
3) Vincoli:
PROBLEMA
Vincolo di capacità
Peso oggetti inseriti < capacità
n
∑ wi xi ≤ B
i =1
MODELLO
ALGORITMI
software
Modello:
PROBLEMA
n
max ∑ pi xi
i =1
n
∑ wi xi ≤ B
MODELLO
i=1
xi ∈{0,1} i = 1,2,...,n
modello di programmazione
lineare intera (binaria)
ALGORITMI
software
3) Applicazione di algoritmi
a) Esatti
PROBLEMA
soluzione ottima
MODELLO
x12 = 0 x12 = 1
Completa enumerazione
Branch-&-Bound
Branch & Cut
Branch-&-Cut
…
x =1 x = 0 x =1
x13 = 0
13
14
14
ALGORITMI
software
b) Euristici
PROBLEMA
soluzione buona
pi -greedy
Greedy
Ext-Greedy
PTAS
FPTAS
…
MODELLO
ALGORITMI
software
Obiettivo ideale:
- Soluzione ottima
- Tempo polinomiale
PROBLEMA
MODELLO
soluzione
ottima
euristica
ALGORITMI
software
0
profitto
tempo
polinomiale
Es: pi - greedy e Greedy
esponenziale
Es: Completa
enumerazione
tempo
Per il problema dello zaino:
Tempo/Sol
Tempo/Sol.
Ottima
Polinomiale
Euristica
pi-greedy
g
y
Greedy
…
Esponenziale
Completa enumerazione
Branch-&-Bound
Branch-&-Cut
…
Algoritmi esatti polinomiali
Non è mai stato ottenuto un algoritmo
in grado di fornire la soluzione ottima
del problema dello zaino in tempi polinomiali
(algoritmo esatto polinomiale)
Inoltre:
Il problema dello zaino è NP-hard
Il problema dello zaino è NP-hard
Appartiene ad una classe di problemi per i quali:
- non è mai stato trovato un algoritmo esatto
p
polinomiale
- se si trovasse un algoritmo esatto polinomiale
per uno di q
p
questi p
problemi,, ogni
g p
problema
della classe avrebbe un algoritmo esatto
p
polinomiale
Teoria della complessità computazionale
È altamente probabile
che un algoritmo
esatto polinomiale
per il problema dello zaino
non esista
PROBLEMA
MODELLO
Potenziare gli
algoritmi esatti
algoritmi euristici
ALGORITMI
software
Algoritmi esatti:
Risolvere all’ottimo
istanze sempre più
grandi
Soluzione ottima in
meno di un secondo!
PROBLEMA
MODELLO
ALGORITMI
software
Algoritmi euristici:
Trovare soluzioni
sempre più
iù vicine
i i
all’ottimo
Garanzie sulla bontà
della soluzione!
PROBLEMA
MODELLO
ALGORITMI
software
4) Utilizzo di software
Gli algoritmi esatti ed
euristici sono implementati
in software
Esatti general purpose:
- Risolutore di Excel
- MPL
- LINGO
PROBLEMA
MODELLO
ALGORITMI
software
PROBLEMA
MODELLO
ALGORITMI
software
Il problema dello zaino e la Logistica
Il problema dello zaino è uno dei sottoproblemi
della logistica
La vera sfida consiste nel trovare la soluzione
migliore per l’intero sistema
13.000 componenti
20.000 fornitori
164 impianti
11.000 rivenditori
PROBLEMA
MODELLO
Risparmio del 26%
g
del costo logistico!
ALGORITMI
software
0
Conclusione
Un antico proverbio recita:
Se un problema non ha
soluzioni, perchè preoccuparsi?
Se un problema ha soluzioni,
perchè preoccuparsi?
Un problema dello zaino con
60 oggetti ha
h
1.152.921.500.000.000.000
soluzioni…
soluzioni
PROBLEMA
MODELLO
ALGORITMI