Ottimizzazione Combinatoria 2

formulazione “Cover” del Knapsack

SARA MATTIA

Università di Roma“La Sapienza”

Dipartimento di Informatica e Sistemistica

Oracolo di Separazione (da max a min)

1)( * uf non esiste nessun cover violato

1)( * uf u* vettore di incidenza di un cover violato

1)( * ug non esiste nessun cover violato

1)( * ug u* vettore di incidenza di un cover violato

𝒇 𝒖∗ = −𝒈 𝒖∗

𝒇 𝒖∗ = 𝒎𝒂𝒙𝒖

𝑖∈𝐽+

𝑥𝑖∗ − 1 𝑢𝑖−

𝑖∈𝐽−

𝑥𝑖∗𝑢𝑖

𝑘∈𝐽+

ത𝑎𝑘𝑢𝑘 +

𝑖∈𝐽−

ത𝑎𝑘𝑢𝑘 ≥ ത𝑏 + 1

𝑢 ∈ 0,1 𝑛

𝒈 𝒖∗ = 𝒎𝒊𝒏𝒖

𝑖∈𝐽−

𝑥𝑖∗𝑢𝑖 −

𝑖∈𝐽+

𝑥𝑖∗ − 1 𝑢𝑖

𝑘∈𝐽+

ത𝑎𝑘𝑢𝑘 +

𝑖∈𝐽−

ത𝑎𝑘𝑢𝑘 ≥ ത𝑏 + 1

𝑢 ∈ 0,1 𝑛

Oracolo «knapsack» approssimato

• 𝒖𝟎 soluzione ottima del rilassamento [ 𝒛𝑳𝑷 = 𝑧 𝒖𝟎 ]

• 𝒖+arrotondamento all’intero superiore

della soluzione ottima 𝒖𝟎 del rilassamento

• 𝒖∗ soluzione ottima del problema (0,1)

𝑘∈𝐽+

ത𝑎𝑘𝑢𝑘 +

𝑖∈𝐽−

ത𝑎𝑘𝑢𝑘 ≥ ത𝑏 + 1

𝑢 ∈ 0,1 𝑛

𝒈 𝒖∗ = 𝒎𝒊𝒏𝒖

𝑖∈𝐽−

𝑥𝑖∗𝑢𝑖 −

𝑖∈𝐽+

𝑥𝑖∗ − 1 𝑢𝑖

𝒈 𝒖𝟎

1n > u > 0n

non esiste nessun cover violato𝒈(𝒖𝟎) ≥ 𝟏

𝒖+ vettore di incidenza di un cover violato𝒈 𝒖+ < 𝟏

Come risolverlo? Simplesso?

No, più semplice …

Rapporto costo/effetto:

nia

cr

i

ii ,,1 ,

Oracolo «knapsack» approssimato

min𝑢

𝑐1𝑢1 + 𝑐2𝑢2 +⋯+ 𝑐𝑛𝑢𝑛

𝑎1𝑢1 + 𝑎2𝑢2 +⋯+ 𝑎𝑛𝑢𝑛 ≥ 𝑏

0 ≤ 𝑢𝑖 ≤ 1 𝑖 = 1,… , 𝑛

min𝑢

𝟐𝑢1 + 𝟓𝑢2 + 𝟓𝑢3 + 𝟏𝟎𝑢4 + 𝑢5

𝟑𝑢1 + 𝟑𝑢2 + 𝟐𝑢3 + 𝟓𝑢4 + 𝟑𝑢5 ≥ 8

33,031

2510

5,225

66,135

66,032

5

4

3

2

1

r

r

r

r

r

Algoritmo Soluzione knapsack “frazionario”

1. Calcola Rapporto costo/effetto ri = ci / ai , i = 1, …. n

2. Costruisci ordinamento = ((1), …, (n)) per rapporti

costo/effetto ri = ci / ai , i = 1, …. N non decrescenti

3. Poni SOMMA := 0 ; k = 1

4. Finchè SOMMA + a(k) ≤ b do

4.1 u(k) := 1

4.2 SOMMA := SOMMA + a(k)

4.3 k := k +1

5. Poni u(k) = (b – SOMMA) / a(k)

)(

)(

)2(

)2(

)1(

)1(

n

n

a

c

a

c

a

c

Esempio

5

54321

54321

}1,0{

835233

10552min

x

xxxxx

xxxxx

33,031

2510

5,225

66,135

66,032

5

4

3

2

1

r

r

r

r

r

{ 5,1,2,4,3 }

0ˆ

0ˆ

33,031ˆ

1ˆ

1ˆ

3

4

2

1

5

x

x

x

x

x

• soluzione del rilassamento:

Esempio: Pianificazione Investimenti – 3 periodi

5

54321

54321

54321

54321

}1,0{

62233

43322

552332

63352max

x

xxxxx

xxxxx

xxxxx

xxxxx

1ˆ

2,0ˆ

8,0ˆ

1ˆ

0ˆ

5

4

3

2

1

x

x

x

x

x

Verifica primo vincolo }5,4,1{1 J

}3,2{1 J

55

44

33

22

11

1

1

xz

xz

xy

xy

xz

1152332 54321 zzyyz

«knapsack» a coefficienti positivi

0 ≤ 𝑥𝑖 ≤ 1 𝑖 = 1,… , 5

Esempio: oracolo «knapsack» approssimato I

1152332 54321 zzyyz

1ˆ

2,0ˆ

8,0ˆ

1ˆ

0ˆ

5

4

3

2

1

x

x

x

x

x

𝑗∈𝐽+

ത𝑎𝑗𝑢𝑗 +

𝑗∈𝐽−

ത𝑎𝑗𝑢𝑗 ≥ ത𝑏 + 1

𝒎𝒊𝒏𝒖

𝑗∈𝐽−

ො𝑥𝑗𝑢𝑗 −

𝑗∈𝐽+

ො𝑥𝑗 − 1 𝑢𝑗

}5,4,1{1 J

}3,2{1 J

5

54321

4321

}1,0{

1252332

8,08,0min

u

uuuuu

uuuu

15 > u > 05

𝑢 ∈ 0,1 𝑛

Esempio: oracolo «knapsack» approssimato II

0

4,052

26,0154

33,031

5,021

5

4

3

2

1

r

r

r

r

r

{ 5,3,2,4,1 }

𝒈 𝒖𝟎 = 1 + 0,8 + 0,4 > 𝟏 nessun cover violato

5

54321

4321

}1,0{

1252332

8,08,0min

u

uuuuu

uuuu

15 > u > 05

𝒈 𝒖𝟎 =

𝒖𝟎𝟓𝒖𝟎𝟑𝒖𝟎𝟐𝒖𝟎𝟒𝒖𝟎𝟏

= 𝟏

= 𝟏

= 𝟏

= 𝟏/𝟐

= 𝟎

Esempio: Prova con il secondo vincolo

5

54321

54321

54321

54321

}1,0{

62233

43322

552332

63352max

x

xxxxx

xxxxx

xxxxx

xxxxx

}5,4,2,1{2 J

}3{2 JVerifica secondo vincolo

1ˆ

2,0ˆ

8,0ˆ

1ˆ

0ˆ

5

4

3

2

1

x

x

x

x

x

0 ≤ 𝑥𝑖 ≤ 1 𝑖 = 1,… , 5

55

44

33

22

11

1

xz

xz

xy

xz

xz

63322 54321 zzyzz

«knapsack» a coefficienti positivi

Esempio: oracolo «knapsack» approssimato I

1ˆ

2,0ˆ

8,0ˆ

1ˆ

0ˆ

5

4

3

2

1

x

x

x

x

x63322 54321 zzyzz

𝑗∈𝐽+

ത𝑎𝑗𝑢𝑗 +

𝑗∈𝐽−

ത𝑎𝑗𝑢𝑗 ≥ ത𝑏 + 1

𝒎𝒊𝒏𝒖

𝑗∈𝐽−

ො𝑥𝑗𝑢𝑗 −

𝑗∈𝐽+

ො𝑥𝑗 − 1 𝑢𝑗

𝑢 ∈ 0,1 𝑛

}5,4,2,1{2 J

}3{2 J

15 > u > 05

5

54321

431

}1,0{

73322

8,08,0min

u

uuuuu

uuu

0

26,0154

4,052

0

1

5

4

3

2

1

r

r

r

r

r

{ 2,5,4,3,1 }

15 > u > 05

5

54321

431

}1,0{

73322

8,08,0min

u

uuuuu

uuu

𝒖+𝟐 = 𝟏

𝒖+𝟓 = 𝟏

𝒖+𝟒 = 𝟏

𝒖+𝟑 = 𝟎

𝒖+𝟏 = 𝟎

𝒖+ =

arrotondamento di 𝒖𝟎

Disequazione

cover violata𝒈 𝒖+ = 𝟎, 𝟖 < 𝟏 z2 +z4 +z5 < 2

𝒈 𝒖𝟎 = 𝟎, 𝟖 ∗ 𝟐/𝟑 < 𝟏

Non possiamo concludere che tutti i «cover»

sono soddisfatti, ma 𝒖+ , vettore di

incidenza del cover 𝟐, 𝟒, 𝟓 , soddisfa:

Esempio: oracolo «knapsack» approssimato II

𝒖𝟎 =

soluzione rilassamento

𝒖𝟎𝟐𝒖𝟎𝟓𝒖𝟎𝟒𝒖𝟎𝟑𝒖𝟎𝟏

= 𝟏

= 𝟏

= 𝟐/𝟑

= 𝟎

= 𝟎

Aggiungi il «cover» e risolvi nuovamente ….

5

54321

54321

54321

54321

}1,0{

62233

43322

552332

63352max

x

xxxxx

xxxxx

xxxxx

xxxxx

x2 +x4 +x5 < 2

0 ≤ 𝑥𝑖 ≤ 1 𝑖 = 1,… , 5

Aggiungi il «cover» e risolvi nuovamente ….

Se il cover violato fosse stato 𝟑, 𝟒, 𝟓 avremmo avuto:

𝒚𝟑 + 𝒛𝟒 + 𝒛𝟓 ≤ 𝟐 (𝟏 − 𝒙𝟑) + 𝒙𝟒 + 𝒙𝟓 ≤ 𝟐

−𝒙𝟑 + 𝒙𝟒 + 𝒙𝟓 ≤ 𝟏