Modelli e Algoritmi per la LogisticaLezione – 9
Formulazione “Cover” - Separazione
ANTONIO SASSANO
Università di Roma“La Sapienza”Dipartimento di Informatica e Sistemistica
Roma, 25-11-99
Formulazione Alternativa (Cover)
xi iC J +
xi < |C|-1-|C J -| iC J -
- per ogni CCai,biPi=xRn
:
P0 ={xRn: Ax<b, 1n > x > 0n} Formulazione Naturale
Cai,bi = insieme dei cover del “knapsack” aTx<bii
Formulazione cover del“knapsack” KPi
P= Pii=0
T
Formulazione cover della Pianificazione Investimenti
• P P0
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 < 2x{0,1}
4
max 3z1 +2z2 +5z3 -6y4+6
2z1 +2z2 +3z3 + 4y4 < 6x{0,1}
4
trasformazione in “knapsack” con coefficienti positivi
{ 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}Cover:
max 3z1 +2z2 + 5z3 -6y4 +6
(z,y){0,1}4
z1 +z2 +z3 < 2
z1 +z2 +y4 < 2
z1 +z3 +y4 < 2z2 +z3 +y4 < 2z3 +y4 < 1
2z1 +2z2 +3z3 + 4y4 < 6
max 3x1 +2x2 + 5x3 +6x4
x{0,1}4
x1 +x2 +x3 < 2x1 +x2 - x4 < 2-1 < 1
x1 +x3 - x4 < 2-1 < 1x2 +x3 - x4 < 2-1 < 1
x3 - x4 < 1-1<0
2x1 +2x2 +3x3 - 4x4 < 2
Oracolo di Separazione delle Disequazioni Cover
xi iC J +
xi < |C|-1-|C J -| iC J -
- per ogni CCai,biPi=xRn
:
Cai,bi = insieme dei cover del “knapsack” aTx<bii
Oracolo diSeparazione
x̂PixRn^
x̂ Pi
iC J -
xixi > |C|-1-|C J -| iC J +
^ ^
Oracolo di Separazione delle Disequazioni Cover
u{0,1}n vettore di incidenza di un cover C
iC J -
xixi > |C|-1-|C J -| iC J +
^ ^
ui xiuixi> ui -1- ui ^ ^iJ + iJ - i
NiJ
-
ui xi uixi> ui -1 ^ ^iJ + iJ - iJ +
Disequazione associata a C violata
La disequazione associata ad un cover C è violata da x se e solo se il vettore di incidenza di C soddisfa la disequazione precedente.
^
^iJ +
( xi -1)uixiui> -1 ^iJ -
• C è un cover del “knapsack” aiTx<bi (aTx<b ) e e solo
se:
Oracolo di Separazione delle Disequazioni Cover (II)
u{0,1}n vettore di incidenza di un cover C
Se a e b sono interi possiamo scrivere:
akukkJ +
akuk> b kJ -
+
akukkJ +
akuk> b+1 kJ -
+
ak kC J +
ak > b kC J -
+ “knapsack” a coefficienti positivi
Oracolo di Separazione delle Disequazioni Cover (III)
Abbiamo dunque:
akukkJ +
akuk > b+1 kJ -
+
u{0,1}n vettore di incidenza di un cover C se e solo se:
B
^iJ +
( xi -1)uixiui> -1 ^iJ -
A
La disequazione associata ad un cover C è violata da x se e solo se il vettore di incidenza di C soddisfa la disequazione:
^
^iJ +
( xi -1)uixiui> -1 ^iJ -
akukkJ +
akuk> b+1 kJ -
+Come trovare il vettore u ?
La disequazione associata ad un cover C è violata da x se e solo se un vettore u{0,1}n soddisfa le disequazioni:
^
u è il vettore di incidenza del cover violato C
Oracolo di Separazione delle Disequazioni Cover (IV)
u* soluzione ottima
z(u)
^iJ +
( xi -1)uixiui> -1 ^iJ -
akukkJ +
akuk> b+1 kJ -
+
u{0,1}n
A
^iJ +
( xi -1)ui xiui ^iJ -
max
akukkJ +
akuk> bi+1 kJ -
+
u{0,1}n
uammissibile z(u) < z(u*)< -1
Se z(u*)<-1
Se z(u*)>-1
Non esiste un vettore u che soddisfa le condizioni A
u* vettore di incidenza di un cover violato da x
^
Nessun cover
è violato da x̂
^iJ +
( xi -1)ui xiui ^iJ -
z(u*)=max
akukkJ +
akuk> b+1 kJ -
+
u{0,1}n
xi iC J +
xi < |C|-1-|C J -| iC J -
- per ogni CCai,biPi=xRn
:
Se z(u*)<-1 xPi^
u* vettore diincidenza di un cover violato da x ^
Se z(u*)>-1 x Pi^
xRn^
Oracolo di Separazione per Pi
u+ vettore diincidenza di un cover violato da x ̂
Se z(u+)>-1 x Pi^
xRn^
Oracolo di Separazione Approssimato per Pi
Se z(u°) <-1 z(u*)< zLP <-1 xPi^
• u° soluzione ottima del rilassamento• u+ arrotondamento all’intero superiore della soluzione ottima del rilassamento
^iJ +
( xi -1)ui xiui ^iJ -
z(u*)=max
akukkJ +
akuk > b+1 kJ -
+
u{0,1}n
z(u°)
1n > u > 0n
PC= Pii=1
T
Poliedro definito dalle (sole) disequazioni “cover”
Oracolo di Separazione per PC
xRn^
i:=i
i=T ?
x̂Pi
i:=i+1 NO SI x̂PC
x̂ Pi
iC J -
xixi > |C|-1-|C J -| iC J +
^ ^^xPC
Oracolo Esatto diSeparazione di Pi
Oracolo diSeparazione
di PC
x* ottima (in Q)
x*PC
x* ottima
Q=
P=
D=A ; d=b
Metodo delSimplesso
min cTx
xQ = Dx<d, (PQ) 1n > x > 0n
x*PC
Nuova D e nuovo d
D d
aiT bi
Aggiunta del vincolo “cover” violato
A b
Disequazioni“cover”
Problema “core”(form. Naturale)
P= Pii=0
TSoluzione del Rilassamento della Formulazione Cover
Esempio: Formulazione cover del “knapsack”
max 3x1 +7x2 +3x3 +5x4 +7x5
x{0,1}5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
15 > x > 05
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
La trasformazione non puo’ essere effettuata su tutto il sistema !
Esaminiamo (e trasformiamo) un “knapsack” alla volta e ai solifini dell’individuazione di vincoli “cover” violati
Oracolo Approssimato:
max (x*1 -1) u1 - x*2 u2 - x*3 u3 + (x*4 -1) u4 + (x*5 -1) u5
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
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
iJ +
( x*i -1)uix*iui iJ -
z(u*)=max
akukkJ +
akuk> b+1 kJ -
+
1n > u > 0n
= max - u2 - u3 - u4 -1/4 u5
2u1 +3u2 +4u3 +3u4 +5u5 > 13
15 > u > 05
Esempio: Formulazione cover del “knapsack”
max 3x1 +7x2 +3x3 +5x4 +7x5
x{0,1}5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
15 > x > 05
Soluzione ottima del rilassamento: x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4 z*=18.25
z1 +4z2 +3y3 +3z4 +4z5 < 8 “knapsack” a coefficienti positivi
Oracolo Approssimato:
max (x*1 -1) u1 +( x*2 -1)u2 - x*3 u3 + (x*4 -1) u4 + (x*5 -1) u5
Soluzione ottima del rilassamento: x*1 =x*2 =x*3 =1; x*4 =0; x*5 =3/4 z*=18.25
z1 +4z2 +3y3 +3z4 +4z5 < 8 “knapsack” a coefficienti positivi
Soluzione: u°1 = u°2 = u°5 =1; u°3 = u°4 = 0
z(u°)=-1/4>-1 x1 +x2 +x5 < 2 Cover violato
iJ +
( x*i -1)uix*iui iJ -
z(u*)=max
akukkJ +
akuk> b+1 kJ -
+
1n > u > 0n
= max - u3 - u4 -1/4 u5
u1 +4u2 +3u3 +3u4 +4u5 > 9
15 > u > 05
Esempio: Formulazione cover del “knapsack”
x{0,1}5
max 3x1 +7x2 +3x3 +5x4 +7x5
2x1 -3x2 -4x3 +3x4 +5x5 < 5
x1 +4x2 -3x3 +3x4 +4x5 < 5
15 > x > 05
Soluzione ottima del rilassamento: x*1 =x*2 =x*3 = x*4 =1; x*5 =0; z*=18
x1 +x2 +x5 < 2
Soluzione ottima del problema intero
Top Related