Divide et Impera

Parte III

Algoritmo di branch-and-bound

Divide et Impera

Sia

z^* = max {c^Tx : x ∈ S} (1)

un problema di OC difficile da risolvere Domanda

Voglio decomporre il problema (1) in una collezione di problemi tali che

1. Ogni nuovo problema sia facile da risolvere

2. Le informazioni che ottengo risolvendo la collezione di problemi mi indicano la sol. ottima di (1)

Un semplice teoremino

Sia S = S₁ ∪ S₂ ∪.. ∪ S_k una decomposizione della regione ammissibile S in k insiemi

Teorema

Se z^h = max {c^Tx : x ∈ S_h} allora z* = max_h z^h Attenzione

Non ho richiesto che S_i ∩ S_j = ∅, ovvero che la decomposizione sia una partizione, ma non ho escluso che possa essere una partizione!

Un esempio

Consideriamo S = {0,1}³

S S₀

x₁=0

S₁

x₁=1

S₀₀

x₂=0

S₀₁

x₂=1

S₁₀

x₂=0

S₁₁

x₂=1

S₀₀₀

x₃=0

S₀₀₁

x₃=1

S₀₁₀

x₃=0

S₀₁₁

x₃=1

S₁₀₀

x₃=0

S₁₀₁

x₃=1

S₁₁₀

x₃=0

S₁₁₁

x₃=1

Attenzione…

Stiamo semplicemente enumerando TUTTI gli insiemi ammissibili!!!!

Per un problema di OC conosciamo bound

“primali” e “duali”

Domanda

Possiamo utilizzare questi bound per enumerare

in modo più efficace?

Altro teoremino

Sia S = S₁ ∪ S₂ ∪.. ∪ S_k una decomposizione della regione ammissibile S in k insiemi.

Sia z^k = max {c^Tx : x ∈ S_k}

Se z^k_LB e z^k_UB sono rispettivamente un lower e un upper bound per z^k

Allora

z_UB = max_k z^k_UB è un upper bound per z^* z_LB = max_k z^k_LB è un lower bound per z^*

Potatura per ottimalità

S ^z_z^{UB= 27}

LB=13

S₀

x₁=0

z ⁰_UB= 20 z ⁰_LB=20

S₁

x₁=1

z ¹_UB= 25 z ¹_LB=15 z_UB= 25

z_LB=20

Potatura per bound

S ^z_z^{UB= 27}

LB=13

S₀

x₁=0

z ⁰_UB= 20 z ⁰_LB=18

S₁

x₁=1

z ¹_UB= 26 z ¹_LB=21 z_UB= 26

z_LB=21

Potatura per inammissibilità

S ^z_z^{UB= 27}

LB=13

S₀

x₁=0

z ⁰_UB= 20 z ⁰_LB=18

S₁

x₁=1

S₁=∅

z_UB= 27 z_LB=18

Nessuna potatura

S ^z_z^{UB= 40}

LB=0

S₀

x₁=0

z ⁰_UB= 20 z ⁰_LB=18

S₁

x₁=1

z ¹_UB= 37 z ¹_LB= 0 z_UB= 37

z_LB=18

Ricapitolando…

Enumero un insieme di soluzioni “implicitamente”

perché “poto” rami dell’albero per:

1. Inammissibilità 2. Bound

3. Ottimalità

Indichiamo con L la lista dei sottoproblemi e con P_i la formulazione del sottoproblema S_i.

L’algoritmo ha il seguente diagramma di flusso:

Branch-and-Bound

Caso 3: Ottimalità

Se P_i ≠ ∅ e la soluzione ottima xⁱ_UB del RL è intera, allora elimina S_i.

Se zⁱ_UB> z^LB allora z^LB =zⁱ_UB, vai a Test Individua una componente frazionaria k di x_i^UBe ramifica S_i aggiungendo ad L S_count+1 = S_i ∩ {x_k= 0}

S_count+2 = S_i ∩ {x_k= 1}

count = count + 2 Caso 2: Bound

Se P_i ≠ ∅, sia zⁱ_UB il valore della soluzione ottima xⁱ_UBdel RL.

Se zⁱ_UB< z^LB elimina S_i per bound, vai a Test

Inizializzazione L=S, z^LB = - ∞ count = 0;

Test: L = ∅?

Scegli un problema S_i dalla lista

Risolvi il Rilassamento Lineare su P_i

Caso 1: Inammissibilità Se P_i = ∅ elimina S_i per inammissibilità, vai a Test

Esempio

Consideriamo il problema di knapsack

max 9 x₁ + 15 x₂ + 8 x₃ + 6 x₄ + 5 x₅ + 4 x₆ + x₇

6 x₁ + 11 x₂ + 6 x₃ + 5 x₄ + 5 x₅ + 4 x₆ + x₇ < 19 (1) x ∈ {0,1}⁷

La soluzione ottima del rilassamento lineare è

x ⁰_UB = (1, 1, 1/3, 0, 0, 0, 0) di valore 26.666 (UB) Possiamo anche inizializzare il LB con la soluzione ammissibile x^LB = (1, 1, 0, 0, 0, 0, 1) di valore 25 Osservazione

Poiché la f.o. ha coefficienti interi, possiamo scrivere la condizione di potatura per bound (caso 2) come ⎣zⁱ_UB⎦ < z^LB

10 8

11 12

4

z ⁴_UB= 25.91

x ⁴_UB = (1, 0.727, 0, 1, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) z ⁰_UB= 26.66

x ⁰_UB = (1, 1, 0.33, 0, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) z ¹_UB= 26.4

x ¹_UB = (1, 1, 0, 0.4, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) z ²_UB= 26.654

x ²_UB = (1, 0.636, 1, 0, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) z ³_UB= 26

x ³_UB = (1, 1, 0, 0, 0.4, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ⁵_UB= 25

x ⁵_UB = (1, 0, 1, 1, 0.4, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ⁶_UB= 26

x ⁶_UB = (0.33, 1, 1, 0, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ⁷_UB= 26

x ⁷_UB = (1, 1, 0, 0, 0, 0.5, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) z ⁸_UB= 24.91

x ⁸_UB = (1, 0.727, 0, 0, 1, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ⁹_UB= 25.4

x ⁹_UB = (0, 1, 1, 0.4, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ¹⁰_UB= ∅

x ¹⁰_UB = (1, 1, 1, 0, 0, 0, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

0

1

3 7

2

5

9 6

Esempio

z ¹¹_UB= 25

x¹¹_UB = (1, 1, 0, 0, 0, 0, 1) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1)

z ¹²_UB= 25.27

x ¹²_UB = (1, 0.81, 0, 0, 0, 1, 0) z ^LB= 25

x ^LB= (1, 1, 0, 0, 0, 0, 1) N.B. In rosso le variabili fissate

Parte IV:

Programmazione dinamica

Esempio

Consideriamo il problema di knapsack:

max 6 x₁ + 10 x₂ + 12 x₃

x₁ + 2x₂ + 3 x₃ < 5 (1) x ∈ {0,1}³

La soluzione ottima è x*⁽¹⁾ = (0, 1, 1), di valore 22.

Consideriamo il problema che si ottiene eliminando l’oggetto 2 e diminuendo il rhs del corrispondente ingombro:

max 6 x₁ + 12 x₃

x₁ + 3 x₃ < 5 – 2 = 3 (2) x ∈ {0,1}²

La soluzione ottima è x^*(2)=(0, 1), di valore 12.

Osservazione

La soluzione x^*(2)= (0, 1) è una “sottosoluzione” di x*⁽¹⁾ = (0, 1, 1), ovvero si ottiene da x*⁽¹⁾ semplicemente eliminando la variabile x₂

Programmazione Dinamica

Schema di principio

Dato un problema di OC, S, la Programmazione Dinamica (PD):

1. Risolve un sottoproblema di S all’ottimo

2. Iterativamente “estende” la soluzione ad S Proprietà fondamentale (optimal substructure)

Sia KP (N, b) un problema di knapsack con soluzione ottima x*.

Consideriamo il problema di knapsack KP(N \ r, b - a_r) che si

ottiene da KP eliminando un qualsiasi oggetto r e diminuendo la capacità dello zaino della quantità a_r.

La soluzione ottima di KP(r, b - a_r) è costituita da x*\x_r .

Notazione

Siano m e d due interi tali che 1 ≤ m ≤ n, 0 ≤ d ≤ b Sia KP (m, d) il problema di knapsack:

KP (m, d) è un sottoproblema di KP, avente soluzione ottima di valore z_m(d).

{ }

m

j

j j

m

j

j j

x

d x

a

x c

1 , 0 max

1

1

∈

∑ ≤

∑

=

=

Programmazione dinamica

Con questo formalismo, il valore della soluzione ottima di KP vale z_n(b).

Calcolo di z

(b)

1. Calcolo z_m(d) per m = {1, …, n}

2. Per ogni m, calcolo z_m(d) per d = {0, …, b}

Osservazione

z_m(d) si calcola in modo ricorsivo se conosco i valori z_m-1(d) per d = {0, …, b}

Formula ricorsiva Condizione iniziale di ricorsione

( ) ⎩ ⎨ ⎧

≥

= <

1 1

1 1

0

a d

per c

a d

d per z

Questa condizione implica:

Se z

(d) = 0 ⇒ x

= 0

Se z

(d) = c

⇒ x

= 1

Formula ricorsiva Formula di ricorsione

{ }

⎩ ⎨

⎧

≥

<

+

= −

−

−

−

m m m

m m

m

m

m

d a

a d

c a

d z

d z

d d z

z se

se )

( ),

( max

) ) (

(

1 1

1

La formula implica:

Se z_m(d) = z_m-1(d) ⇒ x_m = 0 [l’oggetto m NON è stato scelto]

Se z_m(d) = z_m-1(d-a_m) + c_m⇒ x_m = 1 [l’oggetto m È stato scelto]

Esempio max

x₁ + 2x₂ + 3 x₃ < 5 (KP) x ∈ {0,1}³

Calcoliamo la formula di ricorsione per m = 1 z₁(0) = 0 ⇒ x₁= 0

z₁(1) = 6 ⇒ x₁ = 1 z₁(2) = 6 ⇒ x₁ = 1 z₁(3) = 6 ⇒ x₁ = 1 z₁(4) = 6 ⇒ x₁ = 1 z₁(5) = 6 ⇒ x₁ = 1

Esempio

Rappresentiamo questi valori in una tabella di dimensione n × b, in cui ogni elemento contiene z_m(d).

Il simbolo * nella soluzione indica che la variabile non è stata ancora fissata

d

m 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6 2 z₂(0) z₂(1) z₂(2) z₂(3) z₂(4) z₂(5) 3 z₃(0) z₃(1) z₃(2) z₃(3) z₃(4) z₃(5)

Esempio

Calcoliamo ora z₂(d):

Per d = {0, 1}

z₂(0) = z₁(0) = 0 ⇒ x₂= 0 z₂(1) = z₁(1) = 6 ⇒ x₂= 0 Per d = {2, 3, 4, 5}

z₂(2) = max {z₁(2), z₁(0) + c₂} = max{6, 10} = 10 ⇒x₂ = 1 z₂(3) = max {z₁(3), z₁(1) + c₂} = max{6, 16} = 16 ⇒x₂ = 1 z₂(4) = max {z₁(4), z₁(2) + c₂} = max{6, 16} = 16 ⇒x₂ = 1 z₂(5) = max {z₁(5), z₁(3) + c₂} = max{6, 16} = 16 ⇒x₂ = 1 Riportando questi valori in tabella si ha:

Esempio

d

m 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6 2

(0,0,*)

0

(1,0,*)

6

(0,1,*)

10

(1,1,*)

16

(1,1,*)

16

(1,1,*)

16 3 z₃(0) z₃(1) z₃(2) z₃(3) z₃(4) z₃(5)

Esempio

Calcoliamo ora z₃(d):

Per d = {0, 1, 2}

z₃(0) = z₂(0) ⇒ x₃ = 0 z₃(1) = z₂(1) ⇒ x₃ = 0 z₃(2) = z₂(2) ⇒ x₃ = 0

Per d = {3, 4, 5}

z₃(3) = max {z₂(3), z₂(0) + c₃} = max{16, 12} = 16 ⇒x₃ = 0 z₃(4) = max {z₂(4), z₂(1) + c₃} = max{16, 18} = 18 ⇒x₃ = 1 z₃(5) = max {z₂(5), z₂(2) + c₃} = max{16, 22} = 22 ⇒x₃ = 1 Riportando questi valori in tabella si ha:

Esempio

d

m 0 1 2 3 4 5

1

(0,*,*)

0

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6

(1,*,*)

6 2

(0,0,*)

0

(1,0,*)

6

(0,1,*)

10

(1,1,*)

16

(1,1,*)

16

(1,1,*)

16 3

(0,0,0)

0

(1,0,0)

6

(0,1,0)

10

(1,1,0)

16

(1,0,1)

18

(0,1,1)

22

Pertanto, la soluzione ottima è x* = (0, 1, 1) di valore 22.

Algoritmo e complessità

(b) z

max;

(d) z

; c ) a b ( z max

(d);

z max

) c ) a (d z

(d) (z

b a

d

(d) z

(d) z

1 a

0 d

n 2

m

; c (d) z

b a

d

0;

(d) z 1 a 0

d

n m

m m

1 m

1 m

m m

1 m 1

m m

1 m m

m

1 1

1

1 1

return else then if

to for

to for

to for

to for

to for

c) a, b, KP(n, -

DP

=

+

−

=

=

+

−

>

=

=

−

=

=

=

=

=

−

=

−

−

−

−

−

ˆ

Osservazione

La complessità dell’algoritmo è O(nb), ovvero dipende dall’intero b (dimensione dello zaino). In questo caso si dice che l’algoritmo ha complessità pseudo polinomiale.

Parte V:

Rafforzamento di formulazioni e algoritmo del

piano di taglio

Rafforzamento di formulazioni

Il problema di knapsack max 5x₁ + 2x₂

3x₁ + 4x₂ < 6

x ∈ {0,1}² ha come rilassamento lineare max 5x₁ + 2x₂

3x₁ + 4x₂ < 6 x₁ > 0

x₂ > 0 x₁ < 1 x₂ < 1

Indichiamo con x^*_LP la soluzione ottima del rilassamento.

Separazione

Domanda

Possiamo individuare una disequazione valida per conv (F) che “separa” x^*_LP da conv (F) ?

x₂

x^*_LP

x₁

Minimal cover

Consideriamo l’insieme

X = {

Σ

Un insieme C ⊆ N è un cover se e solo se

Σ

Un cover è minimale se, comunque preso j ∈ C, l’insieme C \ { j } NON è un cover

Osservazione

Un cover ha associato un vettore caratteristico non ammissibile per X

Disequazioni cover

Teorema

Se C ⊆ N è un cover, la disequazione

Σ_{j ∈C} x_j < |C| - 1 (*) è valida per conv (X ).

Dimostrazione

Dimostriamo che se x^R ∈ {0,1}ⁿ non soddisfa il vincolo (*) allora x^R

∉ X.

Se x^R è tale che Σ_{j ∈c} x_j > |C| - 1, allora |R ∩ C|= |C|, quindi C ⊆ R.

Pertanto:

Σ

Σ

Σ

ovvero x^R ∉ X. ■

Esempio

Consideriamo il problema di knapsack

max 15 x₁ + 9 x₂ + 8 x₃ + 6 x₄ + 5 x₅ + 4 x₆ + x₇ 11 x₁ + 6 x₂ + 6 x₃ + 5 x₄ + 5 x₅ + 4 x₆ + x₇ < 19 x ∈ [0,1]⁷

x^*_LP = (1, 1, 1/3, 0, 0, 0, 0)

Una disequazione cover violata da x^*_LP è la disequazione x₁ + x₂ + x₃ < 2

Come si individua una disequazione di tipo cover violata da x^*_LP?

Problema di separazione

Domanda

Dato un poliedro P, formulazione di un problema di PL-{0,1}, esiste una disequazione di tipo cover che separa x^*_LP da conv (X)?

Risposta

a) SI la disequazione esiste e fornisce anche il cover associato C

b) NO non esiste

Un algoritmo A che risponde (correttamente) alla

domanda con una delle due risposte possibili a) o b), si chiama ORACOLO DI SEPARAZIONE

Oracolo di separazione

Riscriviamo la disequazione come

La disequazione è violata da x*_LP se e solo se:

Quindi, posso massimizzare la violazione definendo

Un algoritmo per SEP è un oracolo di separazione

⎭⎬

⎫

⎩⎨

⎧ −

=

∑

∈

knapsack di

vincolo del

cover un

è ,

) 1 (

max x_LP^* C SEP

C j

j

∑

>

− +

C j

x j 1) 0 (

1 _LP^*

∑

−

≤

C j

j C

x 1

∑

∈

≤

− +

C j

j C

x | | 0 1

Difatti…

Sia z^*_SEP il valore della soluzione ottima y^*_SEP di

Se 1 + z^*_SEP > 0 allora esiste una disequazione cover violata associata a y^*_SEP

Se 1 + z^*_SEP < 0 allora NON esiste una disequazione cover violata

⎭⎬

⎫

⎩⎨

⎧ −

=

∑

∈

knapsack di

vincolo del

cover un

è ),

1 (

max x_LP^* C SEP

C j

j

Formulazione del problema di separazione

Variabili decisionali

y_j = 1 se l’indice j è nel cover y_j = 0 altrimenti

Funzione obiettivo

Vincoli

j n

j

j

y

x 1 ) (

max

1

*

LP

−

∑

n j n

j

j

y

b y

a

} 1 , 0 {

1

1

∈

+

∑

=

Osservazione

I coefficienti in funzione obiettivo sono < 0, quindi il problema non ammette una soluzione banale

Proprietà del cover

Trasformazione …

Ponendo w_j = 1 – y_j il problema di separazione diventa

ovvero …

n

n

j

j j

n

j

j

j n

j

j n

j

j

w

b a

w a

w x

x

} 1 , 0 {

1 st

) 1 (

) 1 (

max

1 1

1

* LP 1

* LP

∈

+ +

−

≥

−

−

−

−

∑

∑

∑

∑

=

=

=

=

…un problema di knapsack

n n j

j j

n j

j

j n

j

j

w

b a

w a

w x

} 1 , 0 {

1 st

) 1

( max

1 1

1

* LP

∈

−

−

≤

−

∑

∑

∑

=

=

=

Esempio

max 15 x₁ + 9 x₂ + 8 x₃ + 6 x₄ + 5 x₅ + 4 x₆ + x₇ 11 x₁ + 6 x₂ + 6 x₃ + 5 x₄ + 5 x₅ + 4 x₆ + x₇ < 19 x ∈ {0,1}⁷

x^*_LP = (1, 1, 1/3, 0, 0, 0, 0) Problema di separazione

max (1 – 1) w₁ + (1 – 1) w₂ + (1 - 1/3) w₃ + w ₄ + w₅ + w₆ + w₇

11 w₁ + 6 w₂ + 6 w₃ + 5 w₄ + 5 w₅ + 4 w₆ + w₇ <

38 – 19 – 1 = 18 w ∈ {0,1}⁷

Separazione

Problema di separazione

max 2/3 w₃ + w ₄ + w₅ + w₆ + w₇

11 w₁ + 6 w₂ + 6 w₃ + 5 w₄ + 5 w₅ + 4 w₆ + w₇ <

18

w ∈ {0,1}⁷

Soluzione ottima

w* = (0, 0, 0, 1, 1, 1, 1) di valore 4 Riportiamola nello spazio delle y:

y* = (1, 1, 1, 0, 0, 0, 0) di valore -2/3, ovvero < 1

Pertanto…

1. Il valore di 1 + z^*_SEP è > 1, ovvero esiste una disequazione cover violata

2. La disequazione è scritta in corrispondenza agli indici che hanno valore 1 in y^*, ovvero

y* = (1, 1, 1, 0, 0, 0, 0) corrisponde a x₁ + x₂ + x₃ < 2

Ricapitolando

Algoritmo del piano di taglio (CUT)

Dato il rilassamento lineare di un problema di knapsack 1. Calcola la soluzione ottima x^*_LP

2. Se x^*_LP ∈{0, 1}ⁿ STOP altrimenti vai a 3.

3. Definisci il problema di separazione 4. Risolvo il problema di separazione

5. Se esiste una disequazione cover violata la

aggiungo alla formulazione corrente e torno al punto 1, altrimenti STOP

Osservazioni

L’algoritmo del piano di taglio può arrestarsi senza aver trovato la soluzione ottima intera. Che cosa si fa in questo caso?

Algoritmo di Cut-and-branch

Il problema di separazione è un problema di knapsack avente la stessa dimensione del problema originario.

Perché non risolvere all’ottimo direttamente il problema originario?

Cosa succede se si risolve euristicamente il problema di separazione?

Cut-and-branch

Caso 3: Ottimalità

Se P_i ≠ ∅ e la soluzione ottima xⁱ_UB del RL è intera, allora elimina S_i.

Se zⁱ_UB> z^LB allora z^LB =zⁱ_UB, vai a Test Individua una componente frazionaria k di x_i^UBe ramifica S_i aggiungendo ad L S_count+1 = S_i ∩ {x_k= 0}

S_count+2 = S_i ∩ {x_k= 1}

count = count + 2 Caso 2: Bound

Se P_i ≠ ∅, sia zⁱ_UB il valore della soluzione ottima xⁱ_UBdel RL.

Se zⁱ_UB< z^LB elimina S_i per bound, vai a Test

Inizializzazione

z^LB= - ∞; count = 0;

Calcola P, formulazione di S, applicando CUT

L=P

Test: L = ∅?

Scegli un problema S_i dalla lista

Risolvi il Rilassamento Lineare su P_i

Caso 1: Inammissibilità Se P_i = ∅ elimina S_i per inammissibilità, vai a Test

Pianificazione degli investimenti

Dati

I = {1, 2, …, n} insieme di investimenti attivabili su un orizzonte temporale T = {1, 2, …, t} di t periodi

Ad ogni investimento i è associato un indice di redditività c_i

Ogni investimento i genera un flusso di cassa a_i = (a_i1, a_i2, …, a_it) (> 0 introiti, < 0 esborsi) per ogni periodo j ∈ T

Per ogni periodo j ∈ T esiste un budget b_j che limita gli esborsi (flussi di cassa negativi).

Trovare

L’insieme di investimenti I*⊆I che massimizza la redditività con il vincolo che la somma dei flussi di cassa degli investimenti

attivati sia in ogni periodo non superiore al budget b_j

Esempio

Investimento 1

Investimento 2

Investimento 3

Periodo 1 b₁ = -4

Periodo 2 b₂ = -5

Periodo 3 b₃ = -1 a₁₁=2

a₂₁=3

a₃₁=-6

a₁₂=-10

a₂₂=-3

a₃₂=2

a₁₃=-2

a₂₃=5

a₃₃=-3

Esempio

Nell’esempio precedente, se vengono attivati tutti e tre i progetti il vincolo di budget nel periodo 2 NON è

rispettato.

Formulazione

Variabili decisionali

x_j = 1 se il progetto i è attivato x_j = 0 altrimenti

n I

i

j i

ij I i

i i

x

T j

b x

a

x c

} 1 , 0 { max

∈

∈

∀

∑ ≥

∑

∈

∈

Rilassamento lineare

Si vuole migliorare la formulazione

Consideriamo un singolo vincolo di budget e il problema di Knapsack associato (att. al cambio di segno)

1 0

max

≤

≤

≥ x

b Ax

x c

1 0

max

≤

≤

−

≤

−

x

b x

a

x c

j T

j T

(KP

)

Rafforzamento

L’insieme delle soluzioni del problema di

pianificazione è costituito dall’intersezione degli insiemi delle soluzioni dei singoli

problemi di knapsack (KP

) Pertanto

è possibile allora rafforzare ciascun problema

KP

, ad esempio con disequazioni cover, per

ottenere un rafforzamento della formulazione

di pianificazione.

Esempio

Consideriamo il seguente problema di pianificazione:

I = {1, 2, 3, 4, 5}

T = {1, 2, 3}

c = (3, 7, 3, 5, 7) Redditività b = (-2, 0, -5) Budget

a₁ = (-4, 1, -2) Flusso di Cassa I₁ a₂ = (2, -4, 1) Flusso di Cassa I₂ a₃ = (1, 3, -5) Flusso di Cassa I₃ a₄ = (1, -3, -2) Flusso di Cassa I₄ a₅ = (-3, 4, 1) Flusso di Cassa I₅

Esempio

Il rilassamento lineare si scrive (att. al cambio di segno sul vincolo di budget)

1 0

5 2

5 2

0 4

3 3

4

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

≤

≤

≤

− +

+

−

≤

− +

− +

−

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

x x

x x

x

x x

x x

x

(PL)

La soluzione ottima di (PL) è:

09 . 23

1 96

. 0 74

. 0 1

67 .

0

*

5 4

3 2

1

=

=

=

=

=

= z

x x

x x

x

Esempio

Consideriamo a questo punto il primo vincolo di budget:

1 0

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

≤

≤

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

(KP

)

Effettuiamo un cambio di variabili per ottenere tutti coefficienti positivi nel vincolo di knapsack:

J

= {2, 3, 4} ⇒ y

= 1 – x

per ogni i ∈ J

Si ottiene:

6 3

2

4 x

+ y

+ y

+ y

+ x

≤

Esempio

Dobbiamo vedere se esiste una cover violata rispetto alla soluzione:

Risolvendo il problema di separazione (slide 40) si individua la cover violata x₁ + x₅ < 1, che si può aggiungere direttamente alla formulazione, essendo già nelle variabili x.

Osservazione

Se la cover contiene variabili y, bisogna effettuare il cambio di variabile y_h = 1-x_h prima di aggiungere la disequazione alla formulazione

La nuova soluzione ottima del RL (peraltro intera) è

1 04

. 0 96

. 0 1

26 . 0 74

. 0 1 0

1 1 67

. 0

*

*

*

*

*

5 4

3 2

1

=

=

−

=

=

−

=

=

−

=

=

x y

y y

x

22

1

; 1

; 1

; 1

; 0

*

*

*

* 3

* 2

*

1 _{4 5}

=

=

=

=

=

= z

x x

x x

x

Parte VI:

Formulazioni con un numero di vincoli non

polinomiale

Metodo del Simplesso Dinamico Primale

Il metodo del simplesso può essere usato per risolvere un problema di OC qualora sia nota una

rappresentazione del tipo Ax < b (rappresentazione esterna) dell’involucro convesso dei suoi insiemi

ammissibili conv (S).

Domanda

Abbiamo realmente bisogno di una rappresentazione esterna di conv (S)?

Problema del cammino minimo

Sia G = (V, E) un grafo non orientato.

Dati

Coppia di nodi s, t ∈ V

l_uv ∈

R

Determinare un st-cammino di lunghezza totale minima Variabili decisionali

x_ij = 1 se l’arco ij appartiene al cammino st x_ij = 0 altrimenti

st-tagli

Un st-taglio è una partizione (X, V-X) dei vertici di G tale che s ∈ X e t ∈ V-X.

L’insieme K di spigoli con un estremo in X e l’altro in V-X si dicono spigoli del taglio. Si dice peso del taglio la somma dei pesi sugli spigoli in K

Esempio

s t

1 2 3

4

5

6 X = {s, 1, 4, 5} V-X = {2, 3, 6, t} K = {12, 34, 46, 56}

Formulazione

E K uv

uv E uv

uv uv

x

taglio st

K x

x l

} 1 , 0 {

un a

ente corrispond

insieme 1

min

∈

−

∀

∑ ≥

∑

∈

∈

• Ciascun vincolo esprime la condizione che almeno uno spigolo di ogni st-taglio deve appartenere al cammino da s a t.

Osservazioni

• Il numero dei vincoli è esponenziale rispetto alla cardinalità di E.

• Sebbene la matrice dei coefficienti non sia TUM, il rilassamento lineare (PL) di (P) fornisce la soluzione ottima del problema intero.

In pratica, il numero di vincoli rende impossibile “scrivere”

le matrici del metodo del simplesso.

Simplesso Dinamico Primale

Idea

Il simplesso dinamico primale acquisisce le informazioni sulla struttura del poliedro attraverso un oracolo di separazione.

Oracolo di separazione

Dato x* ∈ Rⁿ restituisce una disequazione a^T_i x ≤ b_i del sistema Ax ≤ b violata da x* oppure conclude che tutte le disequazioni del sistema Ax ≤ b sono soddisfatte da x*

x

Algoritmo

Supponiamo di voler risolvere il problema (P)

1 0

max

≤

≤

≤ x

b Ax

x c

dove A è una matrice (m × n) e b ∈

R

Sia D una sottomatrice di A con q << m righe e n colonne. Definiamo il sottoproblema iniziale:

( )

1 0

max

≤

≤

≤ x

d Dx

x

c

P ~

Algoritmo

(P) è

inammissibile Risolvere il problema ( )_P^~

È ammissibile? no

si

= soluzione ottima di ( )^P~

x

Esiste un vincolo violato?

no soluzione ottima di (P)

x

Si aggiunge il vincolo violato a^tx ≤ b₀ a ( )^P~

si

Esempio

s t

2 3

1 4

3

2

1 1

1 1

1

1

Trovare l’st-cammino di lunghezza minima.

Partiamo dalla formulazione:

E uv

x x x

x x

x x

x x

x x

x x

uv t t

s s

t t

s s

∈

∀

≤

≤

≥

+ + ≥

+ +

+ +

+ +

+

1 0

1

1 2

3 min

4 3

2 1

3 4

34 14

23 12

2 1

( ) P ~

Esempio

La soluzione ottima:

0 1

3 34

14 23

12 1

4 2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x x

x x

Oracolo di separazione

Associamo il peso ad ogni arco uv ∈ E e cerchiamo l’st- taglio di peso minimo.

Se il peso di tale taglio è < 1 allora il vincolo relativo è violato da .

Se il peso di K^* è ≥ 1 allora non ci sono disequazioni violate.

x

x

Esempio

s t

2 3

1 4

0

1

0 0

0 0

1

0

X = {s, 2}

K^* = {s1, 12, 23}

Aggiungiamo al problema ( ) il vincolo e risolviamo di nuovo.

23

1

12

1

+ x + x ≥

x

P ~

Esempio

La nuova soluzione ottima è:

0 1

3 34

14 23

1

4 12

2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x

x x

x

s t

2 3

1 4

0

1

0 0

0 1

1

0

X = {s, 1, 2}

K^* = {14, 23}