In tempo di crisi,
per essere + competitivi
si compra in borsa
l’ottimizzazione
ARMONK,NY and PARIS - January 6, 2009.
IBM announced the completion
of its $340 million offer
for the shares of ILOG (NASDAQ: ILOG)
Perche’?
• Perche’ la programmazione matematica
fornisce un approccio metodologico alla
gestione di sistemi complessi di grandi
dimensioni.
• La nostra realta’ economico produttiva e’
estremamente + complessa e articolata
rispetto a pochi decenni fa.
La sfida nella globalizzazione si gioca
su supply chain e innovazione
Logistica e gestione della produzione sono vitali per la
competitivita’ di un’azienda
I sistemi di telecomunicazione
alla base delle piu’semplici attivita’ quotidiane
sono sempre + complessi
Occorrono strumenti di supporto alle decisioni
Il focus si sposta dal
trovare una soluzione
al problema, verso il trovare
la soluzione di costo minimo
fra miliardi di soluzioni possibili
La risposta e’ “ottimizzazione”
per il supporto alle decisioni
• “the science of better decision making“(Jim Orlin)
• “the discipline of applying advanced analytical
methods to help make better decisions. It uses
techniques such as mathematical modeling to
analyze complex situations.”
• Elemento imprescindibile: rappresentazione
matematica dei problemi da affrontare
Le Metodologie analitiche includono
• Simulazione permette di testare la performance di soluzioni
precedentemente elaborate, o prevedere l’effetto di possibili
cambiamenti in un sistema pre-esistente.
• Ottimizzazione restringe la scelta alle sole soluzioni ottime nei casi in
cui le soluzioni possibili sono in numero elevatissimo, tale da escludere
ogni possibilita’ di enumerazione e confronto diretto.
• Teoria dei Giochi fornisce lo strumento matematico per rappresentare
le strategie di comportamento di piu’ soggetti con interessi contrastanti.
• Probabilita’ e Statistica permette di quantificare il rischio, evidenziare
importanti connessioni fra i dati (tecniche di data mining ), verificare le
conclusioni e fare previsioni affidabili, gestire le decisioni in condizioni
di incertezza (teoria delle decisioni).
L’ottimizzazione e’ pervasiva
ha migliorato l’attivita’ di numerose organizzazioni
e realta’ operative presenti tutto intorno a noi.
gli esempi vanno dello
scheduling of airline crews al design delle linee di attesa presso i parchi
di divertimento Disney
al design dei check in degli aereoporti.
dal global resource planning decisions nelle supply chain
fino alla city logistics e nell’ottimizzazione di centinaia di itinerari locali
per operatori nella distribuzione al dettaglio (delivery routes)
negli ultimi anni è stata di supporto allo sviluppo degli strumenti di
pianificazione, gestione, e design delle reti di telecomunicazioni.
Franz Edelman Award
http://www.informs.org/Recognize-Excellence/Franz-Edelman-Award
lista dei vincitori :
•
2013 sistema di distribuzione di riviste di Yedioth, media group in Israele, con riduzione della
sovraproduzione e costi di distribuzione e recupero del non venduto.
•
2012 TNT Express, per network routing e scheduling (TRANS), route planning per pickups e deliveries
(SHORTREC), supply chain (DELTA Supply Chain). Risparmio di €207 milioni tra 2008-2011
•
2011 Midwest ISO azienda produttrice e distributrice di energia per lo scheduling della produzione da
varie fonti, per la distribuzione, e per la definizione delle tariffe.
•
2010 Indeval, maggiore banca di investimenti del Messico ha riorganizzato la propria struttura operativa
basandosi sui dettami della RO
•
2009 Hewlett Packard per la gestione del portafoglio prodotti, valutare a priori un prodotto prima del
lancio e gestirne la complessita’. $500M di incremento nei profitti dal 2005.
•
2008 ferrovie olandesi (Prof. Fischetti, PD) Costruzione dell’orario ferroviario di 5,500 viaggi giornalieri.
Aumento passeggeri e redditivita’.
•
2007 Memorial Sloan-Kettering Cancer Center (localizzazione ottima dei seeds radioattivi nel trattamento
del cancro alla prostata)
•
2006 Warner Robins Air Logistics Center Riduzione del 33% del tempo di inattivita’ degli aereomobili per
manutenzione.
Franz Edelman Award: Altri finalisti
•
SINTEF per l’ottimizzazione della rete offshore per la produzione e il trasporto del gas naturale: SINTEF
ha sviluppato il SSD GassOpt, basato su un modello di programmazione matematica per ottimizzare il
design della rete e il routing del maggior distributore norvegese di gas naturale. Risparmio stimato $1.8
billion US.
•
HERA customer service, rostering del personale (multiobiettivo)
•
CSAV (Compañía Sud Americana de Vapores) gestisce ~700.000 containers operativi in tutto il mondo.
Obiettivo gestire lo sbilanciamento dovuto alla vocazione di alcuni paesi solo esportatori: Cina o
importatori: Saudi Arabia. Problema: dove e quando riposizionare I containers vuoti, e come gestire
l’incertezza della domanda futura.
•
L’agenzia USA per la protezione dell’ambiente (USEPA) ha sviluppato dei sistemi per rilevare e gestire la
contaminazione ambientale di reti idriche, formulando e risolvendo con la programmazione matematica
problemi di placement dei sensori sulla rete e di scheduling degli interventi.
•
Federal Aviation Administration, ha sviluppato il sistema Airspace Flow Program per la gestione ottima dei
ground delays in caso di congestione degli spazi aerei. Risparmi per $118 milioni nel 2006-2007
•
CSX Railway ha sviluppato Dynamic Car Planning System per gestire la riallocazione giornaliera su tutta
la rete ferroviaria US di centinaia di carrozze merci vuote, per soddisfare le domande dei clienti.
•
ZARA ha riorganizzato le politiche distributive dei suoi articoli dai 2 magazzini ai 1500 negozi nel mondo
(1 a Ferrara!!) che permette al singolo punto vendita di personalizzare gli ordini per taglie per ogni
articolo. +4% delle vendite dovuto a questo fattore, $233 nel 2006 e $353 nel 2007.
Come si procede nella risoluzione di un problema:
alla ricerca di una struttura astratta
Esempio:
la schedulazione dei vaccini vs la schedulazione di lavori su macchine
Machine scheduling
Catch-up Scheduling
Similarities
Jobs
Release and due dates
Number of processors
Separation time between jobs
(Chain) Precedence
Vaccine doses
Time Window for each dose
Number of simultaneous administrations
Spacing between doses
Doses must be given in sequence
Dissimilarities
Processing time
Single objective
(makespan, tardiness etc.)
Constant setup or it depends on
previous job
Doses can be administered instantly
Multilevel objective:
Maximize completable vaccination series,
administered doses, total delay.
Spacing may vary by age and depend on when
the previous dose was given
Caratteristiche di un esperto di
ottimizzazione
• Abilita’ nell’ analisi del problema
– Conoscenza del campo di applicazione tramite interazione con
un team di esperti
– Capacita’ di comunicazione per capire e spiegare
• Abilita’ nella costruzione di modelli matematici
– astrazione del problema reale
• Conoscenza delle metodologie della programmazione
matematica per la soluzione dei modelli
• Interpretazione dei risultati del modello teorico nel
problema reale
Approccio alla modellizzazione
dei problemi di ottimizzazione
1.
Definizione di 1 o + OBIETTIVI
….Min costo, max profitto….
2.
Identificazione delle VARIABILI DECISIONALI del
problema
dove localizzare antenne di una rete UMTS
in che turno di lavoro del pilota fare un certo volo
3.
Definizione delle soluzioni ammissibili tramite VINCOLI
MATEMATICI
soddisfare la domanda di traffico, non superare i limiti di legge
per l’inquinamento elettromagnetico
riposo minimo fra 2 voli consecutivi
Pluralita’ di ambiti applicativi
• Impatto sull’efficienza dei sistemi complessi:
esempio: organizzazione di un servizio 118
• E’ critico gestire efficaciemente le risorse
limitate (mezzi, personale, posti letto) per
ottimizzare il servizio e contenere costi
3 livelli decisionali
ove applicare la RO
1) Attività della Centrale Operativa (CO)
2) Attività dei mezzi durante il soccorso
3) Assegnamento del paziente all’ospedale.
Attività della Centrale Operativa
• Operativa: selezione dell’ambulanza a cui
assegnare la chiamata
• Gestionale: Formazione delle squadre
(copertura delle competenze e sinergie),
formazione degli orari e turnazione del
personale delle squadre al centralino.
Attività durante il soccorso
• L’ambulanza inviata raggiunge il paziente in un
tempo che dipende dalla posizione delle
ambulanze e dal percorso scelto  Problemi di
routing su una rete congestionata
• Terminata la missione l’ambulanza va
riassegnata a una colonnina di stazionamento 
problemi di localizzazione delle colonnine
(statico) e di rilocalizzazione delle ambulanze
(dinamico) sul territorio per coprire al meglio il
territorio
Assegnamento del paziente
all’ospedale
Il personale dell’ambulanza è responsabile
del paziente finché il pronto soccorso non
se ne assume la responsabilità e resta in
attesa di un letto disponibile.
Occorre bilanciare il carico tra gli ospedali
senza incrementare eccessivamente la
durata dei viaggi (bi-obiettivo)
Focus
sulla formazione delle squadre
• Il personale e’ organizzato in squadre composte
da un numero prefissato di individui.
• Le competenze individuali sono il + possibile
diversificate nell’ambito della squadra di
appartenenza per includere il massimo delle
competenze possibili.
• Si associa una misura dell’efficienza al singolo
operatore, legata al tempo medio di evasione
delle chiamate nelle serie storiche del servizio.
Problema
Formare le squadre in modo tale da
massimizzarne l’efficienza (intesa come
somma dell’efficienza dei singoli) avendo
la massima ampiezza di competenze.
??? Difficolta’
Garantire la massima equita’ del servizio:
ogni squadra deve essere “al meglio”
Clustering: un possibile modello
Dati p=1..P individui vanno composte t=1..T squadre,
ciascuna con cardinalita’ fissata Mt con t Mt  P
Misura della diversita’ di competenze fra 2 individui
dpq con p, q 1..P, con dpq=dqp > 0 e dpp=0,
Soglia Dt alla minima diversita’ richiesta in ogni team t=1..T
Efficienza individuale: ep  R+ , p=1..P
Variabili decisionali:
xpt =1 se p e’ assegnato alla squadra t, 0 altrimenti
Come ottimizzare la allocazione
dell’efficienza nelle squadre?
• Obiettivo:
– Realizzare una distribuzione equa fra tutte le squadre
Matematicamente, si formalizza minimizzando la somma per ogni squadra dello
scarto quadratico medio fra l’efficienza della squadra pari a Et = p ep xpt e
quella ideale pari all’efficienza media delle squadre, E* = p ep /T.
• Problema:
Min t (Et- E*)2
– t (Et- E*)2 e’ una funzione quadratica
• Soluzione:
– Cercare una funzione lineare o linearizzabile che abbia lo stesso punto di
minimo
– Poiche’ la cardinalita’ di ogni squadra e’ fissata, e nella soluzione ottima
tutte le persone sono coinvolte, una buona approssimazione si ottiene
massimizzando l’efficienza della squadra con efficienza minima.
Modello di NonLinearIntegerProgramming
Max Min t { p epxpt } such that
massimizzo l’efficienza della squadra meno efficiente
t xpt  1  p=1..P ogni individuo al + in 1 squadra
p xpt = Mt  t=1..T ogni squadra ha Mt individui
p q>p (dpqxptxqt)  Dt  t=1..T minima diversita’
xpt  {0, 1}
variabili decisionali
Come linearizzare il modello?
Da NLIP a ILP, un esempio
Ci sono 2 componenti non lineari nel modello
• Funzione obiettivo Max Min diventa
– Max Emin tale che EminEt, Et=p epxpt t
introducendo la nuova variabile Emin e i vincoli di 
• Vincolo quadratico per il prodotto xpt xqt
Nuova variabile ytpq  xpt  xqt definita dal sistema di vincoli
– ytpq  xpt,
– ytpq  xqt,
– ytpq  xpt,+ xqt -1
introducendo la nuova variabile ytpq e il sistema di vincoli che la
legano alle rispettive variabili xpt e xqt
Modello di LinearIntegerProgramming
Max Emin
such that
massimizzo l’efficienza della squadra meno efficiente
livello di efficienza della squadra t
definizione di Emin come minimo degli Et
Et=p epxpt
EminEt
t
t
t xpt  1
p xpt = Mt
 p=1..P ogni individuo al + in 1 squadra
 t=1..T ogni squadra ha Mt individui
p q>p dpq ytpq  Dt  t=1..T
minima diversita’
ytpq  xpt,
con questi vincoli ytpq  xpt  xqt  t,p,q
ytpq  xqt,
ytpq  xpt,+ xqt -1
xpt  {0, 1}
variabili decisionali
Approcci risolutivi
• I migliori solver commerciali di modelli non
gestiscono problemi di dimensioni
significative
• Sviluppo di un approccio ad hoc basato su
una meta-euristica (ricerca Tabu’)
• Miglioramento consistente della situazione
precedente
Localizzazione delle colonnine
• Rilocalizzare le colonnine presenti in citta’ per
migliorare la copertura, sulla base dell’incidenza
di chiamate di diversa entita’ nelle singole zone
(tot chiamate, %codice verde, giallo, rosso)
• I modelli di localizzazione sono spesso utilizzati
per rappresentare problemi di copertura della
domanda nei servizi di pubblica utilita’
Coperura attuale delle colonnine: il raggio dipende dalla velocita’ media nella zona.
Obbligo di intervento entro 8 minuti.
Copertura attuale del territorio
Copertura del territorio dopo la riallocazione
(solo copertura geografica, no info sulla domanda)
Siti di interesse e
di divulgazione della RO
•
•
•
•
•
•
•
Associazione Americana di ricerca Operativa, INFORMS:
www.informs.org (leggere OR-MS today)
www.scienceofbetter.org
http://www.hsor.org/ sull’insegnamento della RO (case
studies interessanti)
www.airo.org
fate le gare! Un utile esercizio
http://www.crema.unimi.it/~righini/GareAIRO/Gare3/
Blog di Michael Trick http://mat.tepper.cmu.edu/blog/
Esempi di applicazione di RO a problemi reali
http://www.dfg-science-tv.de/en/projects/discreteoptimisers (Technical University of Berlin)
http://www.24hor.org/
Pacchetti commerciali di ottimizzazione con
free student edition
• XPress-MP, optimization.fico.com (download free student edition at
http://optimization.fico.com/student-version-of-fico-xpress.html)
• Lindo, www.lindo.com
• Cplex, www.ilog.com,
http://www.ampl.com/DOWNLOADS/cplex80.html
• MINTO http://coral.ie.lehigh.edu/~minto/
• GUROBI, http://gurobi.com/index.html
• SNOPT e MINUS http://www.sbsi-sol-optimize.com/index.htm
(stanford business sw)
• KNITRO www.kiena.com
Fonti:
http://plato.asu.edu/guide.html,
www.mat.univie.ac.at/~neum/glopt/software_g.html
http://www2.informs.org/Resources/Computer_Programs/Online_Optimiz
ers_and_Other_Programs/
Open source optimization codes
Alcune fonti di documentazione per il sw libero:
http://www2.informs.org/Resources/Computer_Programs/Noncommerci
al_Software_Packages_and_Descriptions/
http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html
Consultate la review di sw libero per la programmazione lineare e
lineare intera:
Linderoth, J. T. and Ralphs, T. K. (2005), NoncommercialSoftware for
Mixed-Integer Linear Programming, in Integer Programming:
(piccolo tutorial sui metodi)
http://coral.ie.lehigh.edu/pubs/files/jtl3_noncomm.pdf
Smart Metering
• Schedulazione delle domande di consumo di energia nelle smart
greeds
• Contatori intelligenti, comunicano il consumo in tempo reale alla
contrale operativa e CONTROLLANO l’attivazione di un insieme di
compiti (jobs) le cui richieste vengono inoltrate off line.
• Condomini o comunità abitative, residenziali e uffici, inoltrano alla
centrale un insieme di richieste da soddisfare in modo esatto,
ciascuna con una data potenza da utilizzare e un intervallo di tempo
in cui la richiesta deve essere eseguita  si pone il problema di
distribuire le richieste nel tempo, compatibilmente con le restrizioni
indicate, per attenuare i picchi di consumo dell’energia.
Problema: il costo unitario dell’energia non è
costante ma varia per fasce di consumo
Ogni job j e’ caratterizzato da
una durata dj
un consumo di potenza wj
una finestra temporale [aj, bj]
Per ogni istante t
dell’intervallo di programmazione
ho un carico totale xt
pari alla somma dei carichi dei job
attivi durante l’istante t
d3
d4
w3
w4
a4
a3
b4
b3
d1
d2
a2
w2
w1
a1
b1
RICHIESTE
b3
Tempo
b2
Costo crescente per fascie e costante nella fascia:
funzione a scalino
riflette il costo del produttore
c4
Costo
unitario
c3
c2
c1
s0
s1
s2
s3
Livello di consumo
Funzione costo convessa, lineare a tratti (in ogni fascia):
c4
Come linearizzare
La funzione costo?
Costo
complessivo
Attraverso
variabili binarie
(si/no)
c3
c2
c1
Load totale
s0
s1
0<x1S1
s2
s1<x2 s2
s3
s2<x3 s3
s3<x3 s4
Ogni occorrenza di x
appartiene ad un unico intervallo
x = x1 + x2 + x3 + x4….
y1 + y2 + y3 + y4 = 1
0< x1 s1 y1
c4
c4 x + b4
Costo
complessivo
s1 y2< x2  s2 y2
s2 y3< x3  s3 y3
c3
s3 y4< x3  s4 y4
c3 x + b3
c2 x + b2
s0
c1 x
Load totale
s1
b2
s2
s3
Costo(x) = (y1b1+c1x1) + (y2b2+c2x2) + (y3b3+c3x3) + ….
b3
Modello di programmazione lineare intera
Loadt = x1t + x2t + x3t + x4t…. Loadt = t xit
t
0< x1t  s1 y1t
s1 y2t < x2t  s2 y2t
y1t + y2t + y3t + y4t = 1  t
yit si-1,t  xit  yit si
t i
s2 y3t < x3t  s3 y3t
s3 y4t < x3t  s4 y4t
Costo(Loadt) = (y1tb1+c1x1t) + (y2tb2+c2x2t) + (y3tb3+c3x3t) + ….
CostoTotale = t Costo(Loadt)
Loadt = j ( wj (k=t-dj…dj zjk ))
Obiettivo
Min CostoTotale
zkj =1 se il job j ha inizio al tempo k, =0 altrimenti
aj  startj  bj - dj
Il job va eseguito nella
sua finestra temporale
start j = t (t ztj )
istante di inzio del job j
t ztj = 1  j
ogni job ha un solo istante di inizio