Divide et Impera

(1)

Parte III:

Algoritmo di Branch-and-Bound

(2)

Divide et Impera

Sia

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

un problema di ottimizzazione combinatoria difficile da risolvere.

Domanda: E’ possibile decomporre il problema (1) in una collezione di sottoproblemi tali che

1. ogni nuovo sottoproblema sia facile da risolvere, e

2. le informazioni ottenute risolvendo la collezione di sottoproblemi ci guidino nella ricerca della soluzione ottima di (1)?

(3)

Proposizione: Sia S = S₁ ∪ S₂ ∪… ∪ S_K una decomposizione della regione ammissibile S in K sottoinsiemi, e sia z^h = max {c^Tx : x ∈ S_h}, per h = 1,…,K. Allora z* = max_h z^h.

Osservazione: Non abbiamo richiesto che la decomposizione sia una partizione (ovvero, che S_i∩ S_j = ∅), ma non abbiamo nemmeno escluso che possa esserlo!

Una tipica rappresentazione dell’approccio divide et impera è tramite un albero di enumerazione.

Divide et Impera

(4)

Un esempio

Se S ⊆ {0,1}³, possiamo costruire il seguente albero di enumerazione 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

Le foglie dell’albero corrispondono esattamente ai punti che andremmo a esaminare se potessimo fare un’enumerazione completa.

(5)

Osservazione: Costruendo in questo modo l’albero di enumerazione stiamo semplicemente enumerando TUTTI gli insiemi ammissibili!!!!

Per la maggior parte dei problemi è impossibile effettuare una enumerazione completa.

Poiché per un problema di ottimizzazione combinatoria conosciamo i bound “primali” e i bound “duali”, l’idea è quella di utilizzare tali bound per enumerare gli insiemi ammissibili in modo più efficace.

Divide et Impera

(6)

Proposizione: Sia S = S₁ ∪ S₂ ∪.. ∪ S_K una decomposizione della regione ammissibile S in K sottoinsiemi, e siano

• z^h = max {c^Tx : x ∈ S_h},

• z^h_LB un lower bound per z^h, e

• z^h_UB un upper bound per z^h

per h = 1, …, K. Allora

• z_UB = max_h z^h_UB è un upper bound per z^*, e

• z_LB = max_h z^h_LB è un lower bound per z^*.

Divide et Impera

(7)

Potatura per ottimalità

S₀

z⁰_UB= 27 z⁰_LB=13

Le informazioni su upper e lower bound per il valore ottimo z* permettono di decidere quali nodi dell’albero ha senso continuare ad esaminare per trovare la soluzione ottima.

Poiché z¹_LB = z¹_UB = 20, sicuramente z¹ = 20. Pertanto, non c’è bisogno di esplorare ulteriormente il nodo S₁ che può essere potato per ottimalità.

S₂ x₁=1

z²_UB= 25 z²_LB= 15 S₁

x₁= 0

z¹_UB= 20 z¹_LB=20

(8)

Potatura per ottimalità

S₀

z⁰_UB= 27 z⁰_LB=13

z_LB= 20

Ad ogni passo teniamo traccia di un lower bound globale z_LB. Per il nodo S₀, z_LB = z⁰_LB(alternativamente, z_LB = -∞).

Per ciascun nodo di ogni livello dell’albero, aggiorniamo il valore di z_LB se in corrispondenza di quel nodo abbiamo calcolato un lower bound MIGLIORE (ossia maggiore) di quello corrente.

S₂ x₁=1

z²_UB= 25 z²_LB= 15 S₁

x₁= 0

z¹_UB= 20 z¹_LB=20

= z_LB

(9)

Potatura per bound

S₀

z⁰_UB= 27 z⁰_LB=13

S₂ x₁=1

z²_UB= 26 z²_LB= 21 S₁

x₁= 0

z¹_UB= 20 z¹_LB= 18

Poiché z_LB = 21, la soluzione ottima del problema iniziale ha valore almeno pari a 21. Dal momento che z¹_UB = 20, sicuramente non è possibile ottenere l’ottimo esplorando il nodo S₁. Pertanto, S₁ può essere potato per bound.

z_LB= 21

= z_LB

(10)

Potatura per inammissibilità

S₀

z⁰_UB= 27 z⁰_LB=13

S₂ x₁=1

S₂ = ∅ S₁

x₁= 0

z⁰_UB= 20 z⁰_LB= 18

Poiché il sottoproblema associato al nodo S₂ è inammissibile, non è possibile ottenere l’ottimo esplorando il nodo S₂. Pertanto S₂ può essere potato per inammissibilità.

= z_LB

z_LB= 21

(11)

Nessuna potatura

In questo caso non possiamo fare nessuna osservazione che permetta di potare uno dei due nodi in esame e quindi è necessario esplorare sia S₁ che S₂.

S₀

z⁰_UB= 40 z⁰_LB=0

S₂ x₁=1

z²_UB = 37 z²_LB = 0 S₁

x₁= 0

z¹_UB= 20 z¹_LB= 18

= z_LB

z_LB= 18

(12)

Procedura di Branch-and-Bound

Tramite l’albero di enumerazione, enumeriamo un insieme di soluzioni “implicitamente” perché alcuni rami dell’albero vengono potati per:

1. ottimalità, oppure 2. bound, oppure 3. inammissibilità.

Siano

• L = lista dei sottoproblemi che devono essere risolti

• P_i = formulazione del sottoproblema associato al nodo S_i. L’algoritmo di Branch-and-Bound ha il seguente diagramma di flusso:

(13)

Inizializzazione L=S, z_LB= - ∞ count = 0;

Test: L = ∅?

Scegli un problema S_i dalla lista

Risolvi il Rilassamento Lineare RL_i su P_i

Caso 2: Bound

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

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

Caso 3: Ottimalità

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

Se zⁱ_LB> z_LB allora z_LB =zⁱ_LB,vai a Test

Individua una componente frazionaria k di x_i^UBe ramifica S_iaggiungendo ad L S_count+1= S_i∩ {x_k= 0}

S_count+2= S_i∩ {x_k= 1}

count = count + 2

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

Branch-and-Bound

(14)

Esempio

Consideriamo il problema di knapsack

max 30 x₁ + 36 x₂ + 15 x₃ + 11 x₄ + 5 x₅ + 3 x₆

9 x₁ + 12 x₂ + 6 x₃ + 5 x₄ + 3 x₅ + 2 x₆ < 17 (1) x ∈ {0,1}⁶

La soluzione ottima del Knapsack continuo è

x⁰_UB= (1, 2/3, 0, 0, 0, 0) di valore 54 (z⁰_UB)

Inizializziamo il valore del lower bound uguale al valore di una soluzione ammissibile del problema

x⁰_LB= (1, 0, 0, 0, 0, 0) di valore 30 (z⁰_LB) z_LB = 30

Osservazione: Poiché la funzione obiettivo ha coefficienti interi, possiamo scrivere la condizione di potatura per bound (caso 2) come zⁱ_UB < z_LB.

(15)

S₀

S₁ S₂

z¹_UB= 49.4 z¹_LB= 45

x₂= 0 x₂= 1

z_LB= 45

z⁰_UB = 54

z⁰_LB = 30 = z_LB

z²_UB = 52.6 z²_LB = 36

S₃ S₄

x₄ = 0 x₄= 1

z³_UB = 48.33 z³_LB = 45

z⁴_UB = 48.5

z⁴_LB = 41 S₅ S₆

x₁ = 0 x₁= 1

z⁵_UB = 48.5

z⁵_LB = 36 inammissibilità

×

S₇ S₈

x₅= 0 x₅ = 1

S₇

z⁷_UB = 48 z⁷_LB = 48

×

z_LB = 48 OPT .

z⁸_UB = 47.5 z⁸_LB= 35

bound.

×

^S⁹ ^S¹⁰

x₃ = 0 x₃= 1

z⁹_UB = 46 z⁹_LB = 46

bound .

×

_z10

UB = 36 z¹⁰_LB = 36

bound.

×

^S¹¹ ^S¹²

x₃=0 x₃=1

z¹¹_UB = 47 z¹¹_LB = 47

OPT .

× ×

inammissibilità

Esercizio 1

(16)

Algoritmo di programmazione

dinamica

(17)

Programmazione Dinamica

Schema di principio: Dato un problema di OC, P, la Programmazione Dinamica (PD):

1. Risolve un sottoproblema di P all’ottimo.

2. Iterativamente “estende” la soluzione a P.

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) si ottiene da x^* semplicemente eliminando la variabile x_r .

(18)

Esempio

Consideriamo il seguente problema di knapsack:

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

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

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

Consideriamo il problema che si ottiene eliminando l’oggetto 2 e diminuendo la capacità b del corrispondente ingombro a₂:

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^*(1) = (0, 1, 1), ovvero si ottiene da x*⁽¹⁾ semplicemente eliminando la variabile x₂.

(19)

Notazione

Siano r e d due interi tali che 1 ≤ r ≤ n, 0 ≤ d ≤ b.

Sia KP (r, d) il problema di knapsack:

max

Σ

c_jx_j

Σ

a_jx_j < d x∈ {0, 1}^r

KP (r, d) è un sottoproblema di KP, avente soluzione ottima di valore z_r(d).

r

j = 1 r

j = 1

(20)

Programmazione dinamica

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

Calcolo di z_n(b):

1. Calcolo z_r(d) per r = {1, …, n}.

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

Osservazione:

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

(21)

Formula ricorsiva

( )



≥

= <

1 1

0

a d

per c

a d

d per z

Condizione iniziale di ricorsione:

Questa condizione implica:

• ^{Se z}

₁

(d) = 0 ⇒ x

₁

= 0

• ^{Se z}

₁

^{(d) = c}

₁

⇒ x

₁

= 1

(22)

Formula ricorsiva

Formula di ricorsione:

La formula implica

•

Se z_r(d) = z_r-1(d) ⇒ x_r = 0 [l’oggetto r NON è stato scelto]

•

Se z_r(d) = z_r-1(d–a_r)+c_r ⇒ x_r = 1 [l’oggetto r E’ stato scelto]

z_r(d) =

z_r–1(d) se d < a_r

max{z_r–1(d), z_r–1(d–a_r)+c_r } se d > a_r

(23)

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

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

m m

1 m 1

m

m 1 m m

m

1 1

1

1 1

return else then if

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.

Divide et Impera

Parte III:

Algoritmo di Branch-and-Bound

Divide et Impera

Divide et Impera

Un esempio

Divide et Impera

Divide et Impera

Potatura per ottimalità

Potatura per ottimalità

Potatura per bound

Potatura per inammissibilità

Nessuna potatura

Procedura di Branch-and-Bound

Branch-and-Bound

Esempio

×

×

×

×

×

× ×

Esercizio 1

Algoritmo di programmazione

dinamica

Programmazione Dinamica

Esempio

Notazione

Σ

Σ

Programmazione dinamica

Formula ricorsiva

( )

Condizione iniziale di ricorsione:

Questa condizione implica:

• Se z

(d) = 0 ⇒ x

= 0

• Se z

(d) = c

⇒ x

= 1

Formula ricorsiva

•

•

Algoritmo e complessità

• ^{Se z}

• ^{Se z}

^{(d) = c}