Modelli e Algoritmi per la Logistica
Lezione – 9
Formulazione “Cover” - Separazione
ANTONIO SASSANO
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Roma, 25-11-99
Formulazione Alternativa (Cover)
P0 ={x Rn: Ax<b, 1n > x > 0n} Formulazione Naturale
Cai,bi = insieme dei cover del “knapsack” aiTx<bi
Pi= x Rn :
xi
iC  J +
-
xi
iC  J -
< |C|-1-|C  J -|
per ogni CCai,bi
Formulazione cover del“knapsack” KPi
P
T
P=
i=0
• P P0
i
Formulazione cover della Pianificazione Investimenti
Formulazione migliore di quella Naturale
• Le disequazioni cover appartengono alla formulazione ottima
Esempio: Formulazione cover del “knapsack”
max 3x1 +2x2 +5x3 +6x4
2x1 +2x2 +3x3 - 4x4 < 2
x {0,1}4
trasformazione in “knapsack” con coefficienti positivi
max 3z1 +2z2 +5z3 -6y4+6
2z1 +2z2 +3z3 + 4y4 < 6
x {0,1}4
Cover: { 3,4},{ 1,2,3}, {1,2,4}, {2,3,4}, {1,3,4}, {1,2,3,4}
Cover: { 3,4},{ 1,2,3}, {1,2,4}, {2,3,4}, {1,3,4}, {1,2,3,4}
max 3z1 +2z2 + 5z3 -6y4 +6
2z1 +2z2 +3z3 + 4y4 < 6
z1 +z2 +z3 < 2
z1 +z2 +y4 < 2
z1 +z3 +y4 < 2
z2 +z3 +y4 < 2
z3 +y4 < 1
(z,y) {0,1}4
max 3x1 +2x2 + 5x3 +6x4
2x1 +2x2 +3x3 - 4x4 < 2
x1 +x2 +x3 < 2
x1 +x2 - x4 < 2-1 < 1
x1 +x3 - x4 < 2-1 < 1
x2 +x3 - x4 < 2-1 < 1
x3 - x4 < 1-1<0
x {0,1}4
Oracolo di Separazione delle Disequazioni Cover
Cai,bi = insieme dei cover del “knapsack” aiTx<bi
Pi= x Rn :
x^Rn
xi
iC  J +
Oracolo di
Separazione
-
xi
iC  J -
< |C|-1-|C  J -|
per ogni CCai,bi
x^Pi
x^ Pi
^xi - ^xi
iC  J +
> |C|-1-|C  J -|
iC  J -
Oracolo di Separazione delle Disequazioni Cover
^xi - ^xi
iC  J +
> |C|-1-|C  J -|
iC  J -
Disequazione associata a C violata
u{0,1}n vettore di incidenza di un cover C
ui ^xi
-
ui ^xi
-
iJ +
iJ +
ui ^xi >  ui -1- ui
iJ -
iN
iJ -
ui x^i >  ui -1
iJ -
iJ +
( ^xi -1)ui - ^xi ui > -1
iJ +
iJ -
La disequazione associata ad un cover C è violata da ^
x se e solo se il vettore
di incidenza di C soddisfa la disequazione precedente.
Oracolo di Separazione delle Disequazioni Cover (II)
• C Nè un cover del “knapsack” aiTx<bi (aTx<b ) e e solo se:
ak
kC 
ak
+
J+
kC 
>b
J-
“knapsack” a coefficienti positivi
u{0,1}n vettore di incidenza di un cover C
akuk
kJ +
+
akuk > b
kJ -
Se a e b sono interi possiamo scrivere:
akuk
kJ +
+
akuk > b+1
kJ -
Oracolo di Separazione delle Disequazioni Cover (III)
Abbiamo dunque:
^ se e solo se il vettore
La disequazione associata ad un cover C è violata da x
di incidenza di C soddisfa la disequazione:
A
( ^xi -1)ui - ^xi ui > -1
iJ -
iJ +
u{0,1}n vettore di incidenza di un cover C se e solo se:
B
akuk
kJ +
+
akuk > b+1
kJ -
^ se e solo se un vettore
La disequazione associata ad un cover C è violata da x
u{0,1}n soddisfa le disequazioni:
( ^xi -1)ui - ^xi ui > -1
u è il vettore di incidenza del
cover violato C
iJ +
Come trovare il vettore u ?
kJ +
akuk
iJ -
+
akuk > b+1
kJ -
Oracolo di Separazione delle Disequazioni Cover (IV)
( ^xi -1)ui - ^xi ui > -1
iJ -
iJ +
A
akuk
kJ +
+
akuk>
kJ -
u{0,1}n
z(u)
b+1
max
( ^xi -1)ui
iJ +
akuk
kJ +
+
-
^xi ui
iJ -
akuk> bi+1
kJ -
u {0,1}n
u* soluzione ottima
Se z(u*)<-1
Se z(u*)>-1
u ammissibile
z(u) < z(u*)< -1
Non esiste un vettore
u che soddisfa le
condizioni A
Nessun cover
^
è violato da x
u* vettore di incidenza di un cover violato da x^
Pi= x Rn :
xi
iC  J +
xi
-
iC  J -
< |C|-1-|C  J -|
per ogni CCai,bi
Oracolo di Separazione per Pi
z(u*)=max
( ^xi -1)ui
iJ +
akuk
kJ +
^xRn
+
-
x^i ui
iJ -
akuk > b+1
kJ -
u{0,1}n
Se z(u*)<-1
^x Pi
Se z(u*)>-1
^x  Pi
u* vettore di
incidenza di un
cover violato da ^x
Oracolo di Separazione Approssimato per Pi
z(u*)=max
z(u°)
^xRn
x^i ui
( ^xi -1)ui
-
akuk
akuk > b+1
iJ +
kJ +
+
u{0,1}n
iJ -
kJ -
1n > u > 0n
• u° soluzione ottima del rilassamento
• u+ arrotondamento all’intero superiore
della soluzione ottima del rilassamento
Se z(u°) <-1
z(u*)< zLP <-1
Se z(u+)>-1
^x Pi
^x  Pi
u+ vettore di
incidenza di un
cover violato da ^
x
P
T
PC=
i=1
i
Poliedro definito dalle (sole) disequazioni “cover”
Oracolo di Separazione per PC
x^ Pi
i:=i
^xi
^xRn Oracolo Esatto di
Separazione di Pi
i:=i+1
NO
iC  J +
-
^xi
> |C|-1-|C  J -|
^
xP
C
iC  J -
x^Pi
i=T ?
SI
x^PC
Soluzione del Rilassamento della Formulazione Cover P=
Problema “core”
(form. Naturale)
D=A ; d=b
a iT
bi
i
Disequazioni
“cover”
Nuova D e nuovo d
d
i=0
b
A
min cTx
xQ = Dx<d,
(PQ)
1n > x > 0n
D
P
T
Aggiunta del vincolo “cover” violato
Metodo del
Simplesso
Q= 
x* ottima (in Q)
Oracolo di
Separazione
x*PC
di PC
x*PC
P= 
x* ottima
Esempio: Formulazione cover del “knapsack”
max 3x1 +7x2 +3x3 +5x4 +7x5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
x {0,1}5 15 > x > 05
Soluzione ottima del rilassamento:
x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4
2z1 +3y2 +4y3 +3z4 +5z5 < 12
z*=18.25
“knapsack” a coefficienti positivi
La trasformazione non puo’ essere effettuata su tutto il sistema !
Esaminiamo (e trasformiamo) un “knapsack” alla volta e ai soli
fini dell’individuazione di vincoli “cover” violati
Soluzione ottima del rilassamento:
x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4
z*=18.25
2z1 +3y2 +4y3 +3z4 +5z5 < 12 “knapsack” a coefficienti positivi
Oracolo Approssimato:
z(u*)=max
( x*i -1)ui - x*i ui
iJ +
akuk
kJ +
+
iJ -
akuk > b+1
kJ -
1n > u > 0n
max (x*1 -1) u1 - x*2 u2 - x*3 u3 + (x*4 -1) u4 + (x*5 -1) u5
= max - u2 - u3 - u4 -1/4 u5
2u1 +3u2 +4u3 +3u4 +5u5 > 13
15 > u > 05
Soluzione: u°1 =u°5 =u°3 =1; u°2 =2/3; u°4=0
z(u°)=-2/3-1-1/4=-23/12<-1
Nessun cover violato
Esempio: Formulazione cover del “knapsack”
max 3x1 +7x2 +3x3 +5x4 +7x5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
x {0,1}5 15 > x > 05
Soluzione ottima del rilassamento:
x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4
z1 +4z2 +3y3 +3z4 +4z5 < 8
z*=18.25
“knapsack” a coefficienti positivi
Soluzione ottima del rilassamento:
x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4
z1 +4z2 +3y3 +3z4 +4z5 < 8
Oracolo Approssimato:
z*=18.25
“knapsack” a coefficienti positivi
z(u*)=max
( x*i -1)ui - x*i ui
iJ +
akuk
kJ +
+
iJ -
akuk > b+1
kJ -
1n > u > 0n
max (x*1 -1) u1 +( x*2 -1)u2 - x*3 u3 + (x*4 -1) u4 + (x*5 -1) u5
= max - u3 - u4 -1/4 u5
u1 +4u2 +3u3 +3u4 +4u5 > 9
15 > u > 05
Soluzione: u°1 = u°2 = u°5 =1; u°3 = u°4 = 0
z(u°)=-1/4>-1
x1 +x2 +x5 < 2 Cover violato
Esempio: Formulazione cover del “knapsack”
max 3x1 +7x2 +3x3 +5x4 +7x5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
x1 +x2 +x5 < 2
x {0,1}5
15 > x > 05
Soluzione ottima del rilassamento:
x*1 =x*2 =x*3 = x*4 =1; x*5 =0;
Soluzione ottima del problema intero
z*=18