Parte III:
Algoritmo di Branch-and-Bound
Divide et Impera
Sia
z * = max {c T 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
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)?
Proposizione: Sia S = S 1 ∪ S 2 ∪ … ∪ S K una decomposizione della regione ammissibile S in K sottoinsiemi, e sia z h = max {c T x : 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} 3 , possiamo costruire il seguente albero di enumerazione
S S 0
x 1 =0
S 1 x 1 =1
S 00 x 2 =0
S 01 x 2 =1
S 10 x 2 =0
S 11 x 2 =1
S 000 x 3 =0
S 001 x 3 =1
S 010 x 3 =0
S 011 x 3 =1
S 100 x 3 =0
S 101 x 3 =1
S 110 x 3 =0
S 111 x 3 =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.
Tuttavia…per un problema di ottimizzazione combinatoria conosciamo i bound “primali” e i bound “duali”.
Domanda: Possiamo utilizzare questi bound per enumerare in modo più efficace?
Divide et Impera
Proposizione: Sia S = S 1 ∪ S 2 ∪ .. ∪ S K una decomposizione della regione ammissibile S in K sottoinsiemi, e siano
• z h = max {c T x : 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
Potatura per ottimalità
S
z UB = 27 z LB =13
z UB = max{20, 25} = 25 z LB = max{20, 15} = 20 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 0 LB = z 0 UB = 20, sicuramente z 0 = 20. Pertanto, non c’è bisogno di esplorare ulteriormente il nodo S 0 che può essere potato per ottimalità.
S 1 x 1 =1
z 1 UB = 25 z 1 LB = 15 S 0
x 1 = 0
z 0 UB = 20
z 0 LB =20
Potatura per bound
S
z UB = 27 z LB =13
z UB = max{20, 26} = 26 z LB = max{18, 21} = 21
S 1 x 1 =1
z 1 UB = 26 z 1 LB = 21 S 0
x 1 = 0
z 0 UB = 20 z 0 LB = 18
Poiché la soluzione ottima ha valore almeno pari a 21 e z 0 UB = 20,
sicuramente non è possibile ottenere l’ottimo esplorando il nodo S 0 .
Pertanto, S 0 può essere potato per bound.
Potatura per inammissibilità
S
z UB = 27 z LB =13
S 1 x 1 =1
S 1 = ∅ S 0
x 1 = 0
z 0 UB = 20 z 0 LB = 18
z UB = max{20, 0} = 20 z LB = max{18, 0} = 18
Poiché il sottoproblema associato al nodo S 1 è inammissibile, non è
possibile ottenere l’ottimo esplorando il nodo S 1 . Pertanto, S 1 può essere
potato per inammissibilità.
Nessuna potatura
z UB = max{20, 37} = 37 z LB = max{18, 0} = 18
In questo caso non possiamo fare nessuna osservazione che permetta di potare uno dei due nodi in esame e quindi è necessario esplorare sia S 0 che S 1 .
S
z UB = 40 z LB =0
S 1 x 1 =1
z 1 UB = 37 z 1 LB = 0 S 0
x 1 = 0
z 0 UB = 20
z 0 LB = 18
Ricapitolando…
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
• P i = formulazione del sottoproblema associato al nodo S i .
L’algoritmo ha il seguente diagramma di flusso:
Inizializzazione L=S, z
LB= - ∞ count = 0;
Test: L = ∅?
Scegli un problema S
idalla lista
Risolvi il Rilassamento Lineare su P
iCaso 2: Bound
Se P
i≠ ∅, sia z
iUBil valore della soluzione ottima x
iUBdel RL.
Se z
iUB< z
LBelimina S
iper bound, vai a Test
Caso 3: Ottimalità
Se P
i≠ ∅ e la soluzione ottima x
iUBdel RL è intera, allora elimina S
i.
Se z
iUB> z
LBallora z
LB=z
iUB,vai a Test
Individua una componente frazionaria k di x
iUBe 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
Esempio
Consideriamo il problema di knapsack
max 30 x 1 + 36 x 2 + 15 x 3 + 11 x 4 + 5 x 5 + 3 x 6
9 x 1 + 12 x 2 + 6 x 3 + 5 x 4 + 3 x 5 + 2 x 6 < 17 (1) x ∈ {0,1} 6
La soluzione ottima del rilassamento lineare è
x 0 UB = (1, 2/3, 0, 0, 0, 0) di valore 54 (UB)
Possiamo anche inizializzare il LB con la soluzione ammissibile x LB = (1, 0, 1, 0, 0, 1) di valore 48
Osservazione: Poiché la funzione obiettivo ha coefficienti interi,
possiamo scrivere la condizione di potatura per bound (caso 2)
come z i UB < z LB .
Esempio
S
0z
0UB= 54 z
LB= 48
S
1S
2z
1UB= 49.4 z
1LB= 48
z
2UB= 52.6 z
2LB= 47
S
3S
4S
5S
6S
7S
8S
9S
10S
11S
12z
3UB= 48.33 z
3LB= 48
z
4UB= 48.5 z
4LB= 46
z
5UB= 48.5 z
5LB= 47
z
7UB= 48 z
7LB= 48
z
8UB= 47.5 z
8LB= 35
z
9UB= 46 z
9LB= 46
z
10UB= 36 z
10LB= 16
z
11UB= 47 z
11LB= 47
x
2= 0 x
2= 1
x
4= 0 x
4= 1 x
1= 0 x
1= 1
x
5= 0 x
5= 1 x
3= 0 x
3= 1 x
3=0 x
3=1
inammissibilità ×
×
OPT .
OPT .
OPT .
bound. bound.
inammissibilità
× × × × ×
z
LB= 48 z
LB= 48
z
LB= 48 z
LB= 48 z
LB= 48
z
LB= 48 z
LB= 48 z
LB= 48
Parte IV:
Algoritmo di programmazione
dinamica
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 ) è costituita da x * –x r .
Esempio
Consideriamo il seguente problema di knapsack:
max 6 x
1+ 10 x
2+ 12 x
3x
1+ 2x
2+ 3 x
3< 5 (1) x ∈ {0,1}
3La 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
2:
max 6 x
1+ 12 x
3x
1+ 3 x
3< 5 – 2 = 3 (2) x ∈ {0,1}
2La 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*
(1)semplicemente eliminando la
variabile x
2.
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 j x j
Σ a j x 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
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
( )
≥
= <
1 1
1 1
0
a d
per c
a d
d per z
Condizione iniziale di ricorsione:
Questa condizione implica:
• Se z 1 (d) = 0 ⇒ x 1 = 0
• Se z 1 (d) = c 1 ⇒ x 1 = 1
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 è 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
Esempio
max 6 x 1 + 10 x 2 + 12 x 3
x 1 + 2x 2 + 3 x 3 < 5 (KP) x ∈ {0,1} 3
Calcoliamo la formula di ricorsione per r = 1 z 1 (0) = 0 ⇒ x 1 = 0
z 1 (1) = 6 ⇒ x 1 = 1
z 1 (2) = 6 ⇒ x 1 = 1
z 1 (3) = 6 ⇒ x 1 = 1
z 1 (4) = 6 ⇒ x 1 = 1
z 1 (5) = 6 ⇒ x 1 = 1
Esempio
z 3 (5) z 3 (4)
z 3 (3) z 3 (2)
z 3 (1) z 3 (0)
3
z 2 (5) z 2 (4)
z 2 (3) z 2 (2)
z 2 (1) z 2 (0)
2
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(0,*,*)
1 0
5 4
3 2
1 0
d r
Rappresentiamo questi valori in una tabella di dimensione n × b, in cui ogni elemento contiene z r (d).
Il simbolo * nella soluzione indica che la variabile non è stata
ancora fissata
Esempio
Calcoliamo ora z 2 (d):
Per d = {0, 1}
z 2 (0) = z 1 (0) = 0 ⇒ x 2 = 0 z 2 (1) = z 1 (1) = 6 ⇒ x 2 = 0 Per d = {2, 3, 4, 5}
z 2 (2) = max {z 1 (2), z 1 (0) + c 2 } = max {6, 10} = 10 ⇒x 2 = 1
z 2 (3) = max {z 1 (3), z 1 (1) + c 2 } = max {6, 16} = 16 ⇒x 2 = 1
z 2 (4) = max {z 1 (4), z 1 (2) + c 2 } = max {6, 16} = 16 ⇒x 2 = 1
z 2 (5) = max {z 1 (5), z 1 (3) + c 2 } = max {6, 16} = 16 ⇒x 2 = 1
Riportando questi valori in tabella si ha:
Esempio
z 3 (5) z 3 (4)
z 3 (3) z 3 (2)
z 3 (1) z 3 (0)
3
(1,1,*)
16
(1,1,*)
16
(1,1,*)
16
(0,1,*)
10
(1,0,*)
6
(0,0,*)
2 0
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(0,*,*)
1 0
5 4
3 2
1 0
d
r
Esempio
Calcoliamo ora z 3 (d):
Per d = {0, 1, 2}
z 3 (0) = z 2 (0) ⇒ x 3 = 0 z 3 (1) = z 2 (1) ⇒ x 3 = 0 z 3 (2) = z 2 (2) ⇒ x 3 = 0 Per d = {3, 4, 5}
z 3 (3) = max {z 2 (3), z 2 (0) + c 3 } = max {16, 12} = 16 ⇒x 3 = 0
z 3 (4) = max {z 2 (4), z 2 (1) + c 3 } = max {16, 18} = 18 ⇒x 3 = 1
z 3 (5) = max {z 2 (5), z 2 (2) + c 3 } = max {16, 22} = 22 ⇒x 3 = 1
Riportando questi valori in tabella si ha:
Esempio
(0,1,1)
22
(1,0,1)
18
(1,1,0)
16
(0,1,0)
10
(1,0,0)
6
(0,0,0)
3 0
(1,1,*)
16
(1,1,*)
16
(1,1,*)
16
(0,1,*)
10
(1,0,*)
6
(0,0,*)
2 0
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(1,*,*)
6
(0,*,*)
1 0
5 4
3 2
1 0
d r
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
=
+
−
=
=
+
−
>
=
=
−
=
=
=
=
=
−
=
−
−
−
−
−
