Parte III: Algoritmo di Branch-and-Bound

Parte III:

Algoritmo di Branch-and-Bound

Divide et Impera

Sia

z* = max {c

x : 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

– ogni nuovo sottoproblema sia facile da risolvere, e

– le informazioni ottenute risolvendo la collezione di

sottoproblemi ci guidino nella ricerca della soluzione

ottima di (1)?

Proposizione: Sia S = S

∪ S

∪ … ∪ S

una decomposizione della regione ammissibile S in K sottoinsiemi, e sia z

= max {c

x : x ∈ S

}, per h = 1,…,K. Allora z* = max

z

.

Osservazione: Non abbiamo richiesto che la decomposizione sia una partizione (ovvero, che S

∩ S

= ∅ ), ma non abbiamo nemmeno escluso che possa esserlo!

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

Divide et Impera

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.

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

Proposizione: Sia S = S

∪ S

∪ .. ∪ S

una decomposizione della regione ammissibile S in K sottoinsiemi, e siano

• z

= max {c

x : x ∈ S

},

• z

un lower bound per z

, e

• z

un upper bound per z

per h = 1, …, K. Allora

• z

= max

z

è un upper bound per z

, e

• z

= max

z

è un lower bound per z

.

Divide et Impera

Potatura per ottimalità

S

z

= 27 z

=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

= z

= 20, sicuramente z

= 20. Pertanto, non c’è bisogno di esplorare ulteriormente il nodo S che può essere potato per ottimalità.

S

x

=1

z

= 25 z

= 15

S

x

= 0

z

= 20

z

=20

Potatura per ottimalità

S

z

= 27 z

=13

z

= 20

Ad ogni passo teniamo traccia di un lower bound globale z

. Per il nodo S

, z

= z

(alternativamente, z

= - ∞ ).

Per ciascun nodo di ogni livello dell’albero, aggiorniamo il valore di z

se in corrispondenza di quel nodo abbiamo calcolato un lower bound MIGLIORE (ossia maggiore) di quello corrente.

S

x

=1

z

= 25 z

= 15

S

x

= 0

z

= 20 z

=20

= z

Potatura per bound

S

z

= 27 z

=13

S

x

=1

z

= 26 z

= 21

S

x

= 0

z

= 20 z

= 18

Poiché z

= 21, la soluzione ottima del problema iniziale ha valore almeno pari a 21. Dal momento che z

= 20, sicuramente non è possibile ottenere l’ottimo esplorando il nodo S

. Pertanto, S

può essere potato per bound.

z

= 21

= z

Potatura per inammissibilità

S

z

= 27 z

=13

S

x

=1

S

= ∅

S

x

= 0

z

= 20 z

= 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

z

= 18

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

= 40 z

=0

S

x

=1

z

= 37 z

= 0

S

x

= 0

z

= 20 z

= 18

= z

z

= 18

max 4x ₁ − x ₂ 7x ₁ −2x ₂ ≤14

x ₂ ≤3

2x ₁ −2x ₂ ≤3 x ₁ ≥ 0

x ₂ ≥ 0 x ∈Z ²

1 2

3/2

(20/7,3)

(11/5,7/10) 3

x

x

Esempio

P

Problema al nodo radice S

: Rilassamento lineare di P.

1 2

3/2

x

=(20/7,3)

(11/5,7/10) 3

x

x

Valore dell'UB al nodo radice: z

= 59/7.

Poiché non abbiamo una soluzione ammissibile, fissiamo z

= - ∞

Esempio

S

=S

∩ { ^{x : x}

^≤ ⌊ ^{x }

⌋ }

Esempio

z

= − ∞ = z

S

^z

0

UB

=59/7

Consideriamo la variabile frazionaria x

del vettore x

e generiamo i sottoproblemi di S

applicando la seguente regola di branching:

S

=S

∩ { ^{x : x}

^{≥  x }

^ }

S ₁ =S ₀ ∩ { ^{x : x} 1 ≤ ⌊ ^{20/ 7} ⌋ ⁼² }

S ₂ =S ₀ ∩ { ^{x : x} 1 ≥  20 / 7  =3 }

Memorizziamo S

e S

in una lista di sottoproblemi che devono essere esplorati: L = {S

, S

}

Scegliamo di analizzare il sottoproblema S

.

S

S

S

Esempio

z

= − ∞ = z

z

=59/7

S ₁ =S ₀ ∩ { ^{x : x} 1 ≤ 2 } ^{S 2 =S 0 ∩} { ^{x : x} 1 ≥3 }

Risolviamo il sottoproblema al nodo S

.

max 4x ₁ − x ₂ 7x ₁ −2x ₂ ≤ 14

x ₂ ≤3

2x ₁ −2x ₂ ≤ 3 x ₁ ≤2

x ₁ ≥0 x ₂ ≥0

1 2

3 x

x

Esempio

x

=(2,1/2)

Valore dell'UB per il sottoproblema S

: z

= 15/2.

Poiché non possiamo applicare nessun criterio di potatura, il nodo S

dovrà essere esplorato.

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2

z

= − ∞ = z

Risolviamo il sottoproblema al nodo S

.

max 4x ₁ − x ₂ 7x ₁ −2x ₂ ≤14

x ₂ ≤3

2x ₁ −2x ₂ ≤3 x ₁ ≤2

x ₁ ≥3 x ₁ ≥0 x ₂ ≥0

Esempio

1 2

3 x

x

3

Il sottoproblema al nodo S

è inammissibile!

Il nodo S

può essere chiuso per inammissibilità.

Esploriamo il nodo S

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2

z

= − ∞ = z

Esempio

S ₃ =S ₁ ∩ { ^{x : x} 2 ≤ 0 } ^{S 4 =S 1 ∩} { ^{x : x} 2 ≥1 }

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2

z

= − ∞ = z

S

S

Memorizziamo S

e S

nella lista di sottoproblemi che devono essere esplorati: L = {S

, S

}

Scegliamo di analizzare il sottoproblema S

.

Risolviamo il sottoproblema al nodo S

.

max 4x ₁ − x ₂ 7x ₁ −2x ₂ ≤14 2x ₁ −2x ₂ ≤3

x ₁ ≤2 x ₂ ≤ 0 x ₁ ≥0 x ₂ ≥0

1 2

3 x

x

Esempio

x

=(3/2,0)

Valore dell'UB per il sottoproblema S

: z

= 6.

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2

z

= − ∞ = z

S

S

z

=6

z

= − ∞ = z

Poiché in questo momento non possiamo applicare nessun

criterio di potatura, il nodo S

dovrà essere esplorato.

max 4x ₁ − x ₂ 7x ₁ −2x ₂ ≤14

x ₂ ≤3

2x ₁ −2x ₂ ≤3 x ₁ ≤2

x ₂ ≥1 x ₁ ,x ₂ ≥0

1 2

3 x

x

1

Esempio

Risolviamo il sottoproblema al nodo S

.

x

=(2,1)

Valore dell'UB per il sottoproblema S

: z

= 7.

Osserviamo che la soluzione trovata è intera! Possiamo

aggiornare il valore del lower bound globale!

Il nodo S

può essere chiuso per ottimalità.

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2 z

= − ∞

S

S

z

=6

z

= − ∞ z

=7

z

= 7 = z

In seguito all'aggiornamento del valore del lower bound possiamo chiudere anche il nodo S

per bound. Infatti: z

= 6 < z

.

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2 z

= − ∞

S

S

z

=6

z

= − ∞ z

=7

z

= 7 = z

Poiché non ci sono altri nodi da esplorare nella lista L, l'algoritmo di Branch & Bound termina con la soluzione ottima intera x* = (2, 1) di valore z* = 7.

Esempio

S

S

S

z

= − ∞ = z

z

=59/7

z

=15/2 z

= − ∞

S

S

z

=6

z

= − ∞ z

=7

z

= 7 = z

Procedura di Branch-and-Bound

Tramite l’albero di enumerazione, enumeriamo un insieme di soluzioni

“implicitamente” perché alcuni rami dell’albero vengono potati per:

– ottimalità, oppure – bound, oppure – inammissibilità.

Nella procedura di Branch & Bound è importante

• Scegliere la strategia per il calcolo del bound duale.

• Scegliere la variabile su cui applicare la procedura di branching.

• Scegliere la strategia di esplorazione dell'albero di enumerazione.

Procedura di Branch-and-Bound



Scelta della strategia per il calcolo del bound duale:

EFFICIENZA vs QUALITA' DEL BOUND



Scelta della variabile su cui fare branching:

VARIABILE “PIU' FRAZIONARIA”

(nell'insieme di variabili frazionarie C si sceglie di fare branching sulla variabile j ∈ C in corrispondenza di arg max

min{f

, 1 – f

,}, con f

= x

-  x

 )



Scelta della strategia di esplorazione dell'albero di enumerazione

VISITA IN PROFONDITA' (genera rapidamente una soluzione ammissibile, facile riottimizzazione)

VISITA DEL NODO CON MAX z

(minimizza il numero di sottoproblemi

analizzati)

Procedura di Branch-and-Bound

Siano

• L = lista dei sottoproblemi che devono essere risolti

• P

= formulazione del sottoproblema associato al nodo S

.

L’algoritmo di Branch-and-Bound ha il seguente diagramma di

flusso

Inizializzazione

L=S, z

= - ∞; x* void;

count = 0;

Test: L = ∅ ?

Scegli un problema S

dalla lista

Risolvi il Rilassamento Lineare RL

su P

Caso 2: Bound

P

≠ ∅ , z

valore della soluzione ottima x

di RL

. Se z

< z

elimina S

per bound, vai a Test

Caso 3: Ottimalità

Se P

≠ ∅ e x

è una soluzione ottima intera di Rl

elimina S

per ottimalità.

Se z

> z

allora z

=z

vai a Test Individua una componente frazionaria k di x

e ramifica S

aggiungendo ad L S

= S

∩ {x

= 0}

S

= S

∩ { x

= 1}

count = count + 2

Caso 1: Inammissibilità Se P

= ∅ elimina S

per inammissibilità, vai a Test

Branch-and-Bound

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

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

)

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

x

= (1, 0, 0, 0, 0, 0) di valore 30 (z

) z

= 30

Osservazione: Poiché la funzione obiettivo ha coefficienti interi,

possiamo scrivere la condizione di potatura per bound (caso 2)

come  z

 < z

.

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

z⁹_LB = 46

bound .

×

z¹⁰_LB = 36

bound.

×

^S

^S

OPT .

× inammissibilità ×

Esercizio 1

Algoritmo di programmazione

dinamica

Programmazione Dinamica

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

– Risolve un sottoproblema di P all’ottimo.

– 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

) che si ottiene da KP eliminando un qualsiasi oggetto r e diminuendo la capacità dello zaino della quantità a

.

La soluzione ottima di KP(r, b–a

) si ottiene da x

semplicemente

eliminando la variabile x

.

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

= (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

=(0, 1), di valore 12.

Osservazione: La soluzione x

= (0, 1) è una “sottosoluzione” di x

= (0, 1,

1), ovvero si ottiene da x*

semplicemente eliminando la variabile x

.

Notazione

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

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

max Σ ^p

^x

Σ ^a

^x

^{< d}

x ∈ {0, 1}

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

(d).

j = 1 r

r

j = 1

Programmazione dinamica

Con questo formalismo, il valore della soluzione ottima di KP vale z

(b).

Calcolo di z

(b):

1. Calcolo z

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

2. Per ogni r, calcolo z

(d) per d = {0, …, b}.

Osservazione:

z

(d) si calcola in modo ricorsivo se conosco i valori z

(d)

per d = {0, …, b}.

Formula ricorsiva

z ₁  d  ⁼ { ^{p 0 1 per per d≥a d<a 1 1} }

Condizione iniziale di ricorsione:

Questa condizione implica:

• ^{Se z}

^{(d) = 0} ⇒ x

= 0

• ^{Se z}

^{(d) = p}

⇒ x

= 1

Formula ricorsiva

Formula di ricorsione:

La formula implica

• ^{Se z}

^{(d) = z}

^(d) ⇒ x

= 0 [l’oggetto r NON è stato scelto]

• ^{Se z}

^{(d) = z}

^(d–a

^)+c

⇒ x

= 1 [l’oggetto r E’ stato scelto]

z

(d) =

z

(d) se d < a

max{z

(d), z

(d–a

)+p

} se d > a

Algoritmo e complessità

DP-KP n, b, a, c  for d = 0 to a

− 1

z

 d =0;

for d=a

to b z

 d =p

;

for m=2 to n

for d= 0 to a

−1 z

 d =z

 d 

for d=a

to b

if  z

 d >z

 d−a

 +p

 then max =z

 d ;

else max =z

  b−a

 +p

; z

 d =max;

return z

 b 

Osservazione: La complessità dell’algoritmo è O(nb). Poiché dipende dall’intero b

si dice che l’algoritmo ha complessità pseudo polinomiale.