Metodi di Generazione di Colonne

Generazione di Colonne AA 2009/10
1
Metodi di Generazione di Colonne
Alcuni problemi di programmazione lineare sono caratterizzati da un
elevato numero di variabili e/o vincoli.
Alcuni di questi problemi hanno generalmente una struttura della matrice dei vincoli tale per cui sia possibile risolverli decomponendoli in
sottoproblemi di piú facile soluzione.
In generale l’obiettivo é quello di risolvere tali problemi senza considerare esplicitamente tutti le variabili e/o vincoli del problema.
L’algoritmo che sta alla base dei metodi basati sulla generazione di
colonne é il metodo del simplesso revisionato.
Si consideri la seguente coppia di problemi primale-duale:
(P ) z(P ) = Min cT x
s.t. Ax = b
x≥0
(D) z(D) = Max uT b
s.t. uT A ≤ cT
dove A é una matrice (m × n), e c(n), b(m), x(n) e u(m).
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
2
Sia nel metodo del simplesso primale che in quello duale si eseguono
iterativamente le seguenti operazioni:
(1) Selezione di una colonna s di A;
(2) Selezione di una riga r di A;
(3) Esecuzione di un’operazione di pivoting usando ars come elemento
di pivot.
Nota una base B di A:
- uT = cTB B −1 : variabili duali associate a B;
- b = B −1 b: valore delle variabili in base;
- Aj : colonna j di A;
- cj = cj − uAj : costo ridotto associato alla variabile xj ;
- aij : elemento (i, j) della matrice B −1 A.
Le operazioni del metodo del simplesso primale e duale possono essere
riassunte come segue.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
3
Simplesso primale e duale
Simplesso Primale
Simplesso Duale
Test di ottimalitá
cj ≥ 0, j = 1, . . . , m
bi ≥ 0, i = 1, . . . , m
Var. entrante in base
s = argmin{cj : j = 1, . . . , n}
s = argmin{ |arjj | : arj < 0, j = 1, . . . , n}
c
Var. uscente dalla base r = argmin{ abisi : ais > 0, i = 1, . . . , m}
Elemento di pivoting
ars
r = argmin{bi : i = 1, . . . , m}
ars
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
4
Si noti che nel caso in cui n e/o m siano molto grandi, potrebbe diventare proibitivo effettuare le operazione di pivoting.
Simplesso in formato tableau:
z
-1
0
...
0
x1 . . . xm xm+1 . . . xn
cTB
cTF
B
F
BxB + F xF = b
−z + cTB xB + cTF xF = 0
0
b
xB = b − F xF
−z + cTB B −1 b + (cTF − cB B −1F )xF = 0
−z + c0 + cTF xF = 0
z
-1
0
...
0
x1 . . . xm xm+1 . . . xn
0 ... 0
cTF
−c0
I
F
b
Si noti che non é necessario calcolare A = B −1A ma é sufficiente calcolare B −1 e uT = cTB B −1:
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
5
Il simplesso revisionato
0 ... 0
cTB
cTF
0
I
B
F
b
CARRY
tableau normale
Effettuando i pivot anche sulla matrice CARRY
0 − uI = −u
B −1
CARRY
cTB − uT B = 0
I
cTF − uT F
−uT b
B −1F
B −1 b
tableau normale
Nella matrice CARRY sono memorizzati B −1 e u.
Possiamo eliminare il tableau normale e usare solo la CARRY.
Algoritmo Simplesso Rivisto
1. Calcola i costi cj = cj − uT Aj per ogni j ∈ F ;
2. scegli la variabile entrante xh;
3. genera la sola colonna Ah = B −1Ah e orla la CARRY;
4. scegli la riga t del pivot (criterio del rapporto bi /aih > 0);
5. effettua il pivot sulla CARRY e sulla colonna dei r.h.s.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
−uT
ch
a1h
ath
amh
B −1
6
−uT b
−ue T
−ue T b
B −1b
f −1
B
f −1
B
b
⇒
CARRY orlata
Nuova CARRY
Esempio
0 2 1 0 0
1 2 1 0 6
4 -1 2 1 8

Scelta la base B = [A2, A4] si ha





2 0
1/2 0 
 3 
−1
T
, B
 , u = [1, 0] b = 

B = 
= 
−1 1
1/2 1
11






1 1
1   1/2 
−1 
 = [−1, 0] ⇒(h=1)Ah = B

 = 

cTF = [0, 1]T −[1, 0] 
4 2
4
9/2
CARRY
orlata
B −1
-1 0
1/2 0
1/2 1
Ah
-1
1/2
9/2
b
-6
3
11

⇒
f −1
B
-8/9 2/9
4/9 -1/9
1/9 2/9
f
A
h
0
0
1
be
-32/9
16/9
22/9

1 0
 = [5/9, 2/9]
cTF = [1, 0]T − [8/9, −2/9] 
2 1
Soluzione ottima x1 = 22/9, x2 = 16/9, z = 32/9
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
7
Generazione di Colonne
Dato il seguente problema di programmazione lineare
(P ) z(P ) = Min
s.t.
n
X
j=1
n
X
j=1
cij xj
aij xj = bi,
i = 1, . . . , m
xj ≥ 0, j = 1, . . . , n
abbiamo visto che la soluzione base associata ad una base B di A puó
essere migliorata se posto
∆ = min [cj − cB B −1Aj ]
j=1,...,n
(1)
risulta ∆ < 0.
In generale perció il problema é quello di determinare il valore ∆ del
sottoproblema (1).
Abbiamo visto come questo puó essere fatto per problemi di programmazione lineare utilizzando il simplesso revisionato e che puó risultare
proibitivo se il numero di colonne é elevato.
Vedremo in seguito che per alcuni problemi la struttura del sottoproblema (1) é tale per cui possa essere risolto senza considerare esplicitamente
tutte le variabili j.
Il metodo prende il nome di generazione di colonne (column generation)
perché nella risoluzione del sottoproblema (1) le colonne/variabili del
problema vengono generate solo quando servono.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
Algoritmo Generazione di Colonne
Step 1. Scegli una base ammissibile iniziale B.
Step 2. Calcola xB = B −1 b.
Step 3. Determina la variabile j ∗ con costo ridotto
c∗j = c∗j − cTB B −1 A∗j minimo.
Step 4. Se c∗ ≥ 0 STOP, altrimenti costruisci la
nuova base B e vai allo Step 2.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
8
Generazione di Colonne AA 2009/10
9
Problema del taglio monodimensionale
(Cutting Stock Problem, Gilmore e Gomory (1960))
Sia I un insieme di n oggetti ognuno di lunghezza pari a li, i =
1, . . . , n.
Sia ni il numero di pezzi che si devono produrre per ogni oggetto i,
i = 1, . . . , n.
Sia L la lunghezza delle lastre a disposizione dalle quali tagliare gli
oggetti necessari.
Uno schema di taglio (o pattern) é una possibile configurazione di
taglio degli oggetti I su di una lastra.
Ad esempio, dati i seguenti 3 oggetti:
Oggetto
A
B
C
li
ni
(cm)
5 150
7 200
9 300
e lastre di lunghezza L = 20 cm, alcune configurazioni di taglio sono le
seguenti.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
10
Pattern 1
20
7
9
4
Setting 1
Pattern 2
20
20
5
5
7
3
Setting 2
Pattern 3
20
5
5
9
1
Setting 3
Altre configurazioni:
Pattern 1 Pattern 2 Pattern 3 Pattern 4 Pattern 5
A (5 cm)
0
2
2
4
1
B (7 cm)
1
1
0
0
2
C (9 cm)
1
0
1
0
0
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
11
Sia J l’insieme degli indici di tutte le possibili configurazioni di taglio.
Sia inoltre aij il numero di volte in cui l’oggetto i é tagliato nella configurazione j, i ∈ I, j ∈ J.
L’obiettivo del problema é quello di tagliare dalle lastre tutti i pezzi
necessari minimizzando il numero di lastre necessarie.
Sia yj una variabile non negativa intera rappresentante il numero di
volte che la configurazione j ∈ J é usata per tagliare i pezzi.
La formulazione matematica del problema é la seguente:
X
(P ) M in
j∈J
|
yj
{z
}
numero di lastre
X
j∈J
|
aij yj ≥ ni ,
{z
∀i ∈ I
}
n. di pezzi i
yj ≥ 0 intera ,
∀j ∈ J
Si noti che la cardinalitá dell’insieme J puó essere grande.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
12
Si consideri il rilassamento lineare di P , ovvero:
X
(LP ) M in
j∈J
|
yj
{z
}
numero di lastre
X
j∈J
|
aij yj ≥ ni ,
{z
∀i ∈ I
}
n. di pezzi i
yj ≥ 0,
∀j ∈ J
Sia LP ′ il problema LP dove l’insieme J delle configurazioni é sostituito dall’insieme J ′ ⊂ J (si supponga che J ′ sia tale da garantire che
LP ′ ammette una soluzione ammissibile).
Si risolva il problema LP ′ e siano ui, i ∈ I, la variabile duale associata
ai vincoli di LP ′.
Il costo ridotto di ogni configurazione j ∈ J é dato da:
cj = 1 −
X
i∈I
aij ui
Se risulta
min [cj ] < 0
j∈J\J ′
allora la soluzione base corrente non é ottima per LP.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
13
Siccome i costi ridotti cj , j ∈ J ′ , sono non negativi:
min ′ [1 −
j∈J\J
= min[1 −
j∈J
X
aij ui ]
X
aij ui]
i∈I
i∈I
e ció equivale a risolvere il seguente problema
M in
1−
X
i∈I
X
uizi
lizi ≤ L
i∈I
zi ≥ 0 intera , ∀i ∈ I

















(2)
dove zi , i ∈ I é, rappresenta il numero di volte che l’oggetto i é tagliato
sulla nuova configurazione.
Il problema (2) é equivalente al seguente problema di knapsack intero
X
M ax
i∈I
X
i∈I
uizi
li zi ≤ L
zi ≥ 0 intera , ∀i ∈ I

















Il generatore di colonne é in questo caso un problem di knapsack intero
risolubile in tempo pseudopolinomiale.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
14
Algoritmo generazioni di colonne per il
Cutting Stock Problem
Step 1. Si generi un insieme iniziale J ′ di configurazioni di taglio in
modo tale che il problema LP ′ ammetta una soluzione
ammissibile;
Step 2. Si risolva il problema LP ′ definito sull’insieme di
configurazioni J ′ . Sia x∗ la soluzione ottima primale e
sia u∗ la corrispondente soluzione duale;
Step 3. Si risolva il seguente problema di knapsack intero:









M ax
X
i∈I
X








i∈I
u∗i zi
lizi ≤ L
zi ≥ 0 intera , ∀i ∈ I
Sia z∗ la soluzione ottima.
Step 4. Se
X
i∈I
u∗i zi∗ ≤ 1, stop, x∗ é la soluzione ottima,
altrimenti aggiungi a J ′ la colonna data dalla soluzione z∗
(nuova configurazione) e vai allo Step 2.
Modelli per le Decisioni - M. Dell’Amico/M. Iori
Generazione di Colonne AA 2009/10
15
Branch & Price
Nel caso di problemi di Programmazione Lineare, l’algoritmo column
generation determina la soluzione ottima del problema.
Nel caso di problemi di Programmazione Intera, l’algoritmo column
generation applicato al rilassamento lineare del problema puó terminare
con una soluzione che risulta frazionaria.
In questo caso é necessario applicare un’algoritmo di tipo branch and
bound per determinare la soluzione ottima intera dove il calcolo del lower
bound avviene utilizzando la tecnica column generation.
Questi metodi prendono il nome di metodi branch and price.
Albero decisionale
P0
P1
P2
...
Pq
...
Modelli per le Decisioni - M. Dell’Amico/M. Iori