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