Capitolo 3: Ottimizzazione...
29
Capitolo 3: Ottimizzazione Discreta E. Amaldi DEI, Politecnico di Milano
Transcript of Capitolo 3: Ottimizzazione...
Capitolo 3: Ottimizzazione Discreta
E. AmaldiDEI, Politecnico di Milano
3.1 Modelli di PLI e PLMI
Moltissimi problemi decisionali complessi possono essere formulati come problemi di Programmazione
Lineare in cui tutte (alcune) variabili sono vincolate ad assumere valori interi.
Programmazione Lineare Intera (PLI):
min ctx
Ax ≥ b
x ≥ 0 intere
dove la matrice A e di dimensione m× n, i vettori c e b sono di dimensione n e rispettivamente m.
Se tutte le variabili devono assumere valori binari si tratta Programmazione Lineare Binaria (PL0− 1)
Programmazione Lineare Mista-Intera (PLMI):
min ct1x + ct2y
A1x + A2y ≥ b
x ≥ 0, y ≥ 0 intere
dove le matrici A1 e A2 sono di dimensione m× n1 e rispettivamente m× n2, i vettori c1, c2 e b sono
di dimensione n1, n2 e rispettivamente m.
1
1) Problema di Zaino Binario ”Knapsack”
Un’azienda deve decidere come investire un capitale b.
Sono disponibili n investimenti.
Sia ai la somma da investire nel caso si scelga di effettuare l’i-esimo investimento, con 1 ≤ i ≤ n.
Sia pi il profitto atteso dell’i-esimo investimento.
Problema: determinare quali investimenti effettuare in modo da massimizzare il profitto atteso totale.
2
1) Problema di Zaino Binario ”Knapsack”
Un’azienda deve decidere come investire un capitale b.
Sono disponibili n investimenti.
Sia ai la somma da investire nel caso si scelga di effettuare l’i-esimo investimento, con 1 ≤ i ≤ n.
Sia pi il profitto atteso dell’i-esimo investimento.
Problema: determinare quali investimenti effettuare in modo da massimizzare il profitto atteso totale.
Formulazione di PLI
Variabili di decisione: xi = 1 se si effettua l’i-esimo investimento e xi = 0 altrimenti, con 1 ≤ i ≤ n
max∑n
i=1 pixi∑ni=1 aixi ≤ b
xi ∈ {0, 1} ∀i
Svariate applicazioni dirette e indirette (come sotto-problema)
3
2) Problema di Assegnamento ”Assignment”
Dati n progetti (jobs) e n ingegneri (macchine), supponiamo che ogni progetto possa essere eseguito da
qualsiasi ingegnere.
Sia cij il costo se i-esimo progetto e eseguito dal j-esimo ingegnere, con 1 ≤ i, j ≤ n.
Ogni progetto deve essere assegnato esattamente ad un ingegnere e ogni ingegnere deve vedersi assegnare
esattamente un progetto.
Problema: decidere quale progetto assegnare ad ogni ingegnere in modo da minimizzare il costo totale
necessario per completare tutti i progetti.
Numero di soluzioni ammissibili = n!
4
2) Problema di Assegnamento ”Assignment”
Dati n progetti (jobs) e n ingegneri (macchine), supponiamo che ogni progetto possa essere eseguito da
qualsiasi ingegnere.
Sia cij il costo se i-esimo progetto e eseguito dal j-esimo ingegnere, con 1 ≤ i, j ≤ n.
Ogni progetto deve essere assegnato esattamente ad un ingegnere e ogni ingegnere deve vedersi assegnare
esattamente un progetto.
Problema: decidere quale progetto assegnare ad ogni ingegnere in modo da minimizzare il costo totale
necessario per completare tutti i progetti.
Formulazione di PLI
Variabili di decisione: xij = 1 se i-esimo progetto viene assegnato al j-esimo ingegnere e xij = 0
altrimenti, con 1 ≤ i, j ≤ n
min∑n
i=1
∑nj=1 cijxij
s.v.∑n
i=1 xij = 1 ∀j∑nj=1 xij = 1 ∀i
xij ∈ {0, 1} ∀i,∀j
5
3) Problema di Copertura di un Insieme ”Set Covering”
Siano
• M = {1, 2, . . . ,m} un insieme di clienti
• N = {1, 2, . . . , n} un insieme di siti nei quali si possono localizzare dei centri di servizio
• Mj ⊆M il sottoinsieme di clienti serviti adeguatamente se un centro e localizzato in j, con j ∈ N
• cj il costo di localizzare un centro nel sito j
determinare dove localizzare i centri in modo da servire (”coprire”) tutti i clienti a costo totale minimo.
6
3) Problema di Copertura di un Insieme ”Set Covering”
Siano
• M = {1, 2, . . . ,m} un insieme di clienti
• N = {1, 2, . . . , n} un insieme di siti nei quali si possono localizzare dei centri di servizio
• Mj ⊆M il sottoinsieme di clienti serviti adeguatamente se un centro e localizzato in j, con j ∈ N
• cj il costo di localizzare un centro nel sito j
determinare dove localizzare i centri in modo da servire (”coprire”) tutti i clienti a costo totale minimo.
Formulazione di PLI
Variabili di decisione: xj = 1 se si localizza un centro nel sito j e xj = 0 altrimenti, con 1 ≤ j ≤ n
min∑n
j=1 cjxj
s.v.∑
j:i∈Mjxj ≥ 1 ∀i (1)
xj ∈ {0, 1} ∀j
dove i vincoli (1) sono quelli di copertura
7
”Set covering”:
min
n∑
j=1
cjxj : Ax ≥ e, x ∈ {0, 1}n
dove A = [aij] con aij = 1 se i ∈Mj e aij = 0 altrimenti, ed e = (1, 1, . . . , 1)t
”Set packing”:
max
n∑
j=1
cjxj : Ax ≤ e, x ∈ {0, 1}n
dove i parametri cj rappresentano ”profitti”
”Set partitioning”:
min o max
n∑
j=1
cjxj : Ax = e, x ∈ {0, 1}n
dove i parametri cj possono rappresentare sia ”costi” che ”profitti”
8
4) Problema del Commesso Viaggiatore (asimmetrico) ”Asymmetric TSP”
Dato un grafo orientato G = (V,A), dove V = {1, 2, . . . , n}, con un costo cij ∈ R associato ad ogni
arco (i, j) ∈ A, determinare un ciclo che visita esattamente una volta ogni nodo (ciclo Hamiltoniano)
di costo totale minimo.
9
4) Problema del Commesso Viaggiatore (asimmetrico) ”Asymmetric TSP”
Dato un grafo orientato G = (V,A), dove V = {1, 2, . . . , n}, con un costo cij ∈ R associato ad ogni
arco (i, j) ∈ A, determinare un ciclo che visita esattamente una volta ogni nodo (ciclo Hamiltoniano)
di costo totale minimo.
Se il grafo G e completo, il numero di cicli Hamiltoniani = (n− 1)!
Tipico problema di instradamento
Molte varianti (grafo orientato e non orientato) con vincoli di precedenza, vincoli temporali, piu veicoli
da instradare (”Vehicle Routing Problem”),...
Molteplici applicazioni: logistica, sequenziamento di operazioni,...
Sito web: http://www.tsp.gatech.edu/
10
Una formulazione di PLI
Variabili di decisione: xij = 1 se il ciclo Hamiltoniano contiene l’arco (i, j) e xij = 0 altrimenti, per
(i, j) ∈ A
min∑
(i,j)∈A cijxij
s.v.∑
i: (i,j)∈A xij = 1 ∀j∑j: (i,j)∈A xij = 1 ∀i∑
(i,j)∈A: i∈S, j∈V \S xij ≥ 1 ∀ S ⊂ V, S 6= ∅ (2)
xij ∈ {0, 1} ∀(i, j) ∈ A
dove i vincoli (2) sono i cosiddetti vincoli di taglio (”cut-set inequalities”)
11
Una formulazione di PLI
Variabili di decisione: xij = 1 se il ciclo Hamiltoniano contiene l’arco (i, j) e xij = 0 altrimenti, per
(i, j) ∈ A
min∑
(i,j)∈A cijxij
s.v.∑
i: (i,j)∈A xij = 1 ∀j∑j: (i,j)∈A xij = 1 ∀i∑
(i,j)∈A: i∈S, j∈V \S xij ≥ 1 ∀ S ⊂ V, S 6= ∅ (3)
xij ∈ {0, 1} ∀(i, j) ∈ A
dove i vincoli (3) sono i cosiddetti vincoli di taglio (”cut-set inequalities”)
Formulazione di PLI alternativa contiene, al posto dei vincoli (3), i cosiddetti vincoli di eliminazione
dei sottocicli (”subtour elimination inequalities”):
∑(i,j)∈A: i,j∈S
xij ≤ |S| − 1 ∀ S ⊆ V, 2 ≤ |S| ≤ n− 1 (4)
NB: I vincoli (3) e (4) sono in numero esponenziale rispetto alla dimensione di G
12
5) Mix produttivo con costi fissi
Un’azienda deve decidere quali/quanti articoli produrre il prossimo mese in modo da minimizzare i costi
di produzione soddisfacendo la domanda. Per ogni articolo i, con 1 ≤ i ≤ n, siano ci > 0 il costo
unitario e fi > 0 il costo fisso (se si produce). Inoltre, sia ki > 0 la quantita massima di i-esimo articolo
che puo essere prodotta al mese.
13
5) Mix produttivo con costi fissi
Un’azienda deve decidere quali/quanti articoli produrre il prossimo mese in modo da minimizzare i costi
di produzione soddisfacendo la domanda. Per ogni articolo i, con 1 ≤ i ≤ n, siano ci > 0 il costo
unitario e fi > 0 il costo fisso (se si produce). Inoltre, sia ki > 0 la quantita massima di i-esimo articolo
che puo essere prodotta al mese.
Formulazione di PLMI:
Variabili di decisione:
• xi = quantita di articolo i prodotta, con 1 ≤ i ≤ n
• yi = 1 se xi > 0 e yi = 0 se xi = 0, con 1 ≤ i ≤ n
min∑n
i=1(cixi + fiyi)
s.v. xi ≤ kiyi ∀ivincoli di domanda...
xi ≥ 0 ∀iyi ∈ {0, 1} ∀i
14
5) Mix produttivo con costi fissi
Un’azienda deve decidere quali/quanti articoli produrre il prossimo mese in modo da minimizzare i costi
di produzione soddisfacendo la domanda. Per ogni articolo i, con 1 ≤ i ≤ n, siano ci > 0 il costo
unitario e fi > 0 il costo fisso (se si produce). Inoltre, sia ki > 0 la quantita massima di i-esimo articolo
che puo essere prodotta al mese.
Formulazione di PLMI:
Variabili di decisione:
• xi = quantita di articolo i prodotta, con 1 ≤ i ≤ n
• yi = 1 se xi > 0 e yi = 0 se xi = 0, con 1 ≤ i ≤ n
min∑n
i=1(cixi + fiyi)
s.v. xi ≤ kiyi ∀ivincoli di domanda...
xi ≥ 0 ∀iyi ∈ {0, 1} ∀i
NB: La formulazione non e del tutto esatta, la soluzione xi = 0 e yi = 1 per ogni i e ammissibile per il
PLMI, anche se non puo essere ottima (minimizzazione e costi fissi fi positivi).
15
6) Localizzazione ottima senza vincoli di capacita ”Uncapacitated Facility Location (UFL)”
Siano
• N = {1, 2, . . . , n} un insieme di siti nei quali si possono localizzare dei depositi
• M = {1, 2, . . . ,m} un insieme di clienti
• fj il costo fisso di utilizzo del deposito in j
• cij il costo di trasporto se tutta la domanda del cliente i e soddisfatta dal deposito j,
determinare dove localizzare i depositi in modo da soddisfare la domanda di tutti i clienti minimizzando
i costi (costi di trasporto e costi di utilizzo).
16
Formulazione di PLMI
Variabili di decisione:
• xij = frazione della domanda del cliente i soddisfatta dal deposito j, con 1 ≤ i ≤ m e 1 ≤ j ≤ n
• yj = 1 se si utilizza il deposito j e yj = 0 altrimenti, con 1 ≤ j ≤ n
min∑
i∈M∑
j∈N cijxij +∑
j∈N fjyj
s.v.∑
j∈N xij = 1 ∀i ∈M∑i∈M xij ≤ myj ∀j ∈ N (5)
yj ∈ {0, 1} ∀j ∈ N
0 ≤ xij ≤ 1 ∀i ∈M, j ∈ N
con n vincoli (5) che legano le variabili xij e yj
NB: Se di indica la domanda del cliente i e kj la capacita del deposito j, gli eventuali vincoli di capacita:∑i∈M
dixij ≤ kjyj ∀j ∈ N
17
7) Pianificazione della produzione ”Uncapacitated Lot-Sizing (ULS)”
Un’impresa deve pianificare la produzione di un solo tipo di prodotto per i prossimi n mesi. Si suppone
che il magazzino sia vuoto all’inizio del periodo di pianificazione e che alla fine del periodo debbano
rimanere in magazzino 50 unita.
Siano
• ft il costo fisso di produzione durante il periodo t
• pt il costo unitario di produzione durante il periodo t
• ht il costo unitario di immagazzinamento durante il periodo t
• dt domanda per il periodo t
determinare un piano di produzione per i prossimi n mesi che permetta di minimizzare i costi (produzione
e magazzino) soddisfacendo la domanda ad ogni periodo.
Formulare il problema come un PLMI.
18
Formulazione di PLMI
Variabili di decisione:
• xt = quantita prodotta durante il periodo t, con 1 ≤ t ≤ n
• st = quantita in magazzino alla fine del periodo t, con 0 ≤ t ≤ n
• yt = 1 se si attiva la produzione durante il periodo t e yj = 0 altrimenti, con 1 ≤ t ≤ n
min∑n
t=1 ptxt +∑n
t=1 htst +∑n
t=1 ftyt
s.v. st = st−1 + xt − dt ∀txt ≤Myt ∀t
s0 = 0, sn = 50, st, xt ≥ 0 ∀tyt ∈ {0, 1} ∀t
dove M > 0 un limite superiore sulla massima quantita prodotta durante ogni periodo.
NB: Se sn = 0, anche xt ≤ (∑n
t dt)yt.
Inoltre e possibile sostituire st =∑t
i xi −∑t
i di
19
3.2 Formulazioni alternative ed ideali
In Programmazione Lineare (PL) le migliori formulazioni sono le piu compatte (con il minor numero di
variabili/vincoli) visto che la complessita computazionale dei problemi cresce polinomialmente con n e
m. La scelta della formulazione non determina la possibilita di risolvere o meno il problema.
La situazione e molto diversa per i problemi di PLI e PLMI: estese campagne computazionali indicano
che la scelta della formulazione e cruciale.
Per capire cosa caratterizza le buone formulazioni, partiamo dal concetto di rilassamento continuo
(lineare) di un PLI o PLMI.
20
Definizione: Dato un qualsiasi problema di PLMI (PLI)
zPLMI = min ct1x + ct2y
s.v. A1x + A2y ≥ b (6)
x ≥ 0, y ≥ 0 intere (7)
il suo rilassamento continuo (lineare) e il seguente problema di PL:
zPL = min ct1 + ct2y
s.v. A1x + A2y ≥ b (8)
x ≥ 0, y ≥ 0 (9)
dove il vincolo di interezza sulle variabili yj e omesso.
Se una variabile intera yj nel PLMI e tale che 0 ≤ yj ≤ uj, nel rilassamento continuo yj ∈ [0, uj].
Sia XPLMI la regione ammissibile del PLMI definita da (6)-(7) e XPL quella del rilassamento continuo
definita da (8)-(9).
Conseguenze: Poiche XPLMI ⊆ XPL e i problemi sono di minimizzazione, abbiamo:
• zPL ≤ zPLMI , ovvero zPL e un limite inferiore rispetto a zPLMI ;
• se una soluzione ottima x∗PL del rilassamento continuo e ammissibile per il PLI/PLMI di partenza,
e anche ottima per quest’ultimo.
Se il PLMI e di massimizzazione, chiaramente zPLMI ≤ zPL.
21
Qualsiasi problema di PLI/PLMI ammette un numero infinito di formulazioni corrette alternative con
regioni ammissibili del rilassamento continuo diverse.
Definizione: Un poliedro P ⊆ Rn+p (sottoinsieme definito da un numero finito di vincoli lineari) e
una formulazione di un insieme X ⊆ Rn × Zp se e solo se X = P ∩ (Rn × Zp).
NB: Nel caso dei costi fissi, non abbiamo considerato l’insieme X = {(0, 0), (xi, 1) per 0 < x ≤ ki} ma
X ∪ {(0, 1)}.
Esempi:
1) Due formulazioni alternative per il TSP con vincoli di taglio o di eliminazione di sotto-cicli.
2) Formulazione di PLMI alternativa per il problema UFL:
min∑
i∈M∑
j∈N cijxij +∑
j∈N fjyj
s.v.∑
j∈N xij = 1 ∀i ∈M
xij ≤ yj ∀i ∈M, j ∈ N (10)
yj ∈ {0, 1} ∀j ∈ N
0 ≤ xij ≤ 1 ∀i ∈M, j ∈ N
con mn vincoli (10) che legano le variabili xij e yj.
22
Le formulazioni alternative possono adoperare variabili aggiuntive o variabili diverse. Nel primo caso si
parla di formulazioni estese.
Esempio:
Formulazione di PLMI estesa per il problema ULS
Variabili di decisione:
• wit = quantita prodotta durante il periodo i e venduta durante il periodo t, con 1 ≤ i ≤ t ≤ n
• yt = 1 se si attiva la produzione durante il periodo t e yj = 0 altrimenti, con 1 ≤ t ≤ n
min∑n
i=1
∑nt=i citwit +
∑nt=1 ftyt
s.v.∑t
i=1wit = dt ∀twit ≤ dtyi ∀i, t, i ≤ t
xi =∑n
t=iwit ∀i (11)
wit ≥ 0 ∀i, t, i ≤ t
yt ∈ {0, 1} ∀t
con i costi aggregati (produzione e magazzino) cit = pi + hi + . . . + ht−1.
NB: I vincoli (12) esprimono le ”vecchie” variabili xi in funzione delle ”nuove” wit.
23
Definizione: Dato un insieme convesso C ⊆ Rn, x ∈ C e un un punto estremo se non puo essere
espresso come combinazione convessa di due punti distinti di C.
Sia X = {x1, . . . , xk} l’insieme delle soluzioni ammissibili di un PLI. Supponiamo che X sia limitato e
quindi un insieme finito.
Teorema: conv(X) e un poliedro e i punti estremi di conv(X) appartengono a X .
Questo risultato, che vale anche per insiemi X illimitati di punti interi e di punti misti interi, implica:
min{ctx : x ∈ X} = min{ctx : x ∈ conv(X)}
In teoria, il problema di PLI/PLMI si puo ricondurre ad un singolo problema di PL!
In pratica, anche per X limitato, la formulazione ideale e spesso di dimensione esponenziale o difficile
da determinare.
Chiaramente la regione ammissibile P di qualsiasi rilassamento continuo soddisfa: conv(X) ⊂ P .
Definizione:
• La formulazione ideale di un insieme X ⊆ Rn e il poliedro conv(X).
• Dato un insieme X ⊆ Rn e due formulazioni P1 e P2 di X , la formulazione P1 domina (e piu
stringente di) quella P2 se P1 ⊂ P2.
24
1) Localizzazione ottima senza vincoli di capacita ”Uncapacitated Facility Location (UFL)”
Proprieta: Il rilassamento continuo della formulazione di PLMI alternativa (con i vincoli xij ≤ yj)
domina quello della prima formulazione di PLMI (con i vincoli aggregati∑
i∈M xij ≤ myj).
Siano
P1 ={
(x, y) ∈ Rnm+n :∑
j∈N xij = 1 ∀i, xij ≤ yj ∀i,∀j, 0 ≤ xij ≤ 1 ∀i,∀j, 0 ≤ yj ≤ 1 ∀j}
e
P2 ={
(x, y) ∈ Rnm+n :∑
j∈N xij = 1 ∀i,∑
i∈M xij ≤ myj ∀j, 0 ≤ xij ≤ 1 ∀i,∀j, 0 ≤ yj ≤ 1 ∀j}
,
chiaramente P1 ⊆ P2 (sommando gli m vincoli xij ≤ yj per un dato j si ottiene∑
i∈M xij ≤ myj per
quel j).
Inoltre e facile esibire un (x, y) che appartiene a P2 ma non appartiene a P1
2) TSP simmetrico
Confronto tra le due formulazioni alternative nella prima serie di esercizi
25
Confronto tra formulazioni con variabili diverse
Consideriamo una prima formulazione con tutte variabili intere (PLI)
min{ctx : x ∈ P1 ∩ Zn1}
con P1 ⊆ Rn1, e una formulazione estesa
min{ct(x,w) : (x,w) ∈ P2 ∩ (Zn1 × Rn2)}
con P2 ⊆ Rn1 × Rn2.
Definizione: Dato un insieme convesso P ⊆ Rn1 × Rn2, la proiezione di P sul sottospazio Rn1 e
Πx(P ) = {(x ∈ Rn1 : (x,w) ∈ P per qualche w ∈ Rn2}
Per confrontare una formulazione P1 ⊆ Rn1 e una formulazione estesa P2 ⊆ Rn1×Rn2, si confrontando
quindi P e Πx(P2).
26
Come determinare le proiezioni dei poliedri sui sottospazi di Rn?
Metodo di eliminazione di Fourier-Motzkin (inizio 800):
Prima procedura per risolvere sistemi di disuguaglianze lineari
Descrizione
Ad ogni iterazione viene eliminata una variable, combinando in tutti i modi possibili le disuguaglianze
correnti (complessita esponenziale).
Esempio
27
Confronto con formulazione estesa: Pianificazione della produzione (ULS)
Confrontiamo la formulazione P1 descritta da
st = st−1 + xt − dt ∀txt ≤Myt ∀t
s0 = 0, st, xt ≥ 0 ∀t0 ≤ yt ≤ 1 ∀t
e Πx,s,y(P2), con P2 descritto da ∑ti=1wit = dt ∀twit ≤ dtyi ∀i, t, i ≤ t
xi =∑n
t=iwit ∀i (12)
wit ≥ 0 ∀i, t, i ≤ t
0 ≤ yt ≤ 1 ∀t
E’ facile verificare che Πx,s,y(P2) ⊂ P1. Ad esempio, il punto xt = dt, yt = dt/M per ogni t e un punto
estremo di P1 che non appartiene a Πx,s,y(P2).
Inoltre P2 e la formulazione ideale, ovvero descrive il guscio convesso di tutte le soluzioni ammissibili di
ULS.
28
