Parte III: Algoritmo di Branch-and-Bound

Parte III:

Algoritmo di Branch-and-Bound

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

– ogni nuovo sottoproblema sia facile da risolvere, e

– le informazioni ottenute risolvendo la collezione di sottoproblemi ci guidino nella ricerca della soluzione ottima del problema (1)?

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

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

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

Potatura per ottimalità

S₀

z⁰_UB= 27 z⁰_LB=13

z_LB= 20

Ad ogni passo teniamo traccia di un lower bound globale z_{L B}. Per il nodo S₀ , z_{L B} = z⁰_{L B} (alternativamente, z_{L B} = -∞).

Per ciascun nodo di ogni livello dell’albero, aggiorniamo il valore di z_{L B} 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

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

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= 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⁰_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

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⁰_UB=(20/7,3)

(11/5,7/10) 3

x₂

x₁

Valore dell'UB al nodo radice: z⁰_UB = 59/7.

Poiché non abbiamo una soluzione ammissibile, fissiamo z⁰_LB = - ∞

Esempio

S₁ =S₀∩

{

⌊

⌋ }

Esempio

z⁰_LB= − ∞ = z_LB

S₀ ^z

0

UB=59/7

Consideriamo la variabile frazionaria x₁ del vettore x⁰_UB e generiamo i sottoproblemi di S₀ applicando la seguente regola di branching:

S₂ =S₀∩

{

⌈

⌉ }

S₁ =S₀∩

{

⌊

⌋

}

S₂=S₀∩

{

⌈

⌉

}

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⁰_LB= − ∞ = z_LB z⁰_UB=59/7

S₁=S₀∩

{

}

{

}

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¹_UB=(2,1/2)

Valore dell'UB per il sottoproblema S₁: z¹_UB = 15/2.

Poiché non possiamo applicare nessun criterio di potatura, il nodo S₁ dovrà essere esplorato.

Esempio

S₀

S₁ S₂

z⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2

z¹_LB= − ∞ = z_LB

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⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2

z¹_LB= − ∞ = z_LB

Esempio

S₃=S₁∩

{

}

{

}

S₀

S₁ S₂

z⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2

z¹_LB= − ∞ = z_LB

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³_UB=(3/2,0)

Valore dell'UB per il sottoproblema S₃: z³_UB = 6.

Esempio

S₀

S₁ S₂

z⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2

z¹_LB= − ∞ = z_LB

S₃ S₄

z³_UB=6

z³_LB= − ∞ = z_LB

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⁴_UB=(2,1)

Valore dell'UB per il sottoproblema S₄: z⁴_UB = 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⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2 z¹_LB= − ∞

S₃ S₄

z³_UB=6

z³_LB= − ∞ z⁴_UB=7

z⁴_LB= 7 = z_LB

In seguito all'aggiornamento del valore del lower bound possiamo chiudere anche il nodo S₃ per bound. Infatti: z³_UB = 6 < z⁴_LB.

Esempio

S₀

S₁ S₂

z⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2 z¹_LB= − ∞

S₃ S₄

z³_UB=6 z³_LB= − ∞

z⁴_UB=7

z⁴_LB= 7 = z_LB

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⁰_LB= − ∞ = z_LB z⁰_UB=59/7

z¹_UB=15/2 z¹_LB= − ∞

S₃ S₄

z³_UB=6 z³_LB= − ∞

z⁴_UB=7

z⁴_LB= 7 = z_LB

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 di esplorazione dell'albero di enumerazione

VISITA DEL NODO CON MAX z_UB

(Vantaggio: limita il numero di nodi visitati

Svantaggio: si impiega più tempo per generare soluzioni ammissibili.)

VISITA IN PROFONDITA'

(Vantaggi: genera rapidamente una soluzione ammissibile, limita la memoria necessaria per memorizzare l'albero delle soluzioni

Svantaggio: rischio di esplorare completamente sotto-alberi con soluzioni scadenti)

Procedura di Branch-and-Bound

Siano

• P₀ = problema di ottimizzazione iniziale associato al nodo S₀.

• L = lista dei sottoproblemi che devono essere risolti

• P_i = formulazione del sottoproblema associato al nodo S_i.

L'algoritmo di Branch-and-Bound può essere schematizzato come segue.

Procedura di Branch-and-Bound

Step 0. Inizializzazione: L = S₀; z_LB = – ∞(max); x* = 0.

Step 1. Criterio di arresto: Se L = ∅, allora STOP: x* è la soluzione ottima.

Step 2. Selezione del nodo: Seleziona il sottoproblema P_i (nodo S_i) da esplorare dalla lista L.

Step 3. Bounding: Risolvi un rilassamento di P_i. Step 4. Fathoming:

● Se P_i non è ammissibile, elimina P_i da L e vai allo Step 1.

● Se zⁱ_UB < z_LB, elimina P_i da L e vai allo Step 1.

● Se xⁱ_UB è intera, elimina P_i da L. Se, inoltre, zⁱ_LB > z_LB, aggiorna z_LB e vai allo Step 1.

Step 5. Branching: Individua una componente frazionaria di xⁱ_UB e genera i sottoproblemi di P da aggiungere alla lista L. count = count+1. Vai allo Step 1.

Inizializzazione

L=S₀, z_LB= - ∞; x* = 0;

Test: L = ∅?

Scegli un problema P_i dalla lista

Risolvi un Rilassamento di P_i

Caso 2: Bound

P_i ≠ ∅, zⁱ_UB valore della soluzione ottima xⁱ_UB di RL_i. Se zⁱ_UB < z_LB elimina P_i per bound, vai a Test

Caso 3: Ottimalità

Se P_i ≠ ∅ e xⁱ_UB è una soluzione ottima intera di Rl_i elimina P_i per ottimalità.

Se zⁱ_LB > z_LB allora z_LB =zⁱ_LB, vai a Test Individua una componente frazionaria k di x_i^UB e ramifica P_i aggiungendo i nuovi sottoproblemi ad L. vai a Test

Caso 1: Inammissibilità Se P_i = ∅ elimina P_i 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⁰_{U B} = (1, 2/3, 0, 0, 0, 0) di valore 54 (z⁰_{U B})

Inizializziamo il valore del lower bound uguale al valore di una soluzione ammissibile del problema x⁰_{L B} = (1, 0, 0, 0, 0, 0) di valore 30 (z⁰_{L B}).

Inizializziamo il valore del lower bound globale z_{L B} = 30.

Osservazione: Poiché la funzione obiettivo ha coefficienti interi, possiamo scrivere la condizione di potatura per bound (caso 2) come zⁱ_{U B} < z_{L B}.

Esercizio 1

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

z⁸_UB = 47.5 z⁸_LB = 35

bound.

×

×

bound. bound.

×

Algoritmo di programmazione

dinamica

Programmazione Dinamica

Schema di principio: Sia P un problema di OC. 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_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 .

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₂.

Notazione

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

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

max

Σ

Σ

x∈ {0, 1}^r

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

j = 1 r

r j = 1

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}.

Formula ricorsiva

z₁





{

}

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

•

•

z_r(d) =

z_r–1 (d) se d < a_r

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

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_m−1 z_md =z_m−1d 

for d=a_m to b

if  z_m−1d >z_m−1d−a_m+p_m then max =z_m−1d ;

else max =z_m−1 b−a_m+p_m; z_md =max;

return z_nb 

Osservazione: La complessità dell’algoritmo è O(nb). Poiché dipende dall’intero b si dice che l’algoritmo ha complessità pseudo polinomiale.