Branch and Bound
Branch-and-bound
Un esempio di problema di PLI:
P
0: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 x
1, x
2≥ 0
x
1, x
2∈ I
Continua
Risoluzione (grafica) del rilassamento lineare P
0′di P
0.
000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000
111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111
u1
u2 A
B
C D
- +
z
u3
1 1
2 3 4 5 6
2 4
3
Continua
S
ott= {A} A = 5
4 , 15 4
Valore ottimo= U (P
0) =
504U (P
0) = upper bound o limitazione superiore del valore
ottimo di P
0Divide et impera: Branching
Suddivisione del problema originario in due sottoproblemi P
1e P
2. Come?
Seleziono, secondo una determinata regola, una variabile x
icon valore non intero x
∗inella soluzione ottima del
rilassamento lineare di P
0e:
creo P
1aggiungendo ai vincoli di P
0, il vincolo x
i≤ ⌊x
∗i⌋ ; creo P
2aggiungendo ai vincoli di P
0, il vincolo
x
i≥ ⌊x
∗i⌋ + 1
Esistono molte regole di scelta della variabile. Qui ne useremo una semplicissima non preoccupandoci
dell’efficienza: seleziona quella con valore non intero nel
Nell’esempio
Sottoproblema P
1P
1: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′4) x
1≤ 5
4
= 1 x
1, x
2≥ 0
x
1, x
2∈ I
Nell’esempio
Sottoproblema P
2P
2: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′′4) x
1≥ 5
4
+ 1 = 2 x
1, x
2≥ 0
x
1, x
2∈ I
Lower Bound
LB = Lower bound o limitazione inferiore del valore ottimo di P
0. È un qualsiasi valore che soddisfa:
LB ≤ opt(P
0) = valore ottimo P
0Come si ottiene?
Se durante l’esecuzione dell’algoritmo (tipicamente durante la risoluzione dei rilassamenti lineari di P
0e dei suoi
sottoproblemi) si osserva il valore della funzione obiettivo cx nei punti y
1, . . . , y
h∈ Z
a, ciascuno di questi valori è
utilizzabile come lower bound, in quanto: cy
i≤ opt(P
0) per i = 1, . . . , h . Per avere un valore di lower bound il più vicino possibile a opt(P
0) si pone:
LB = max{cy
i: i = 1, . . . , h}
Rilassamento lineare di P 1
000000 000000 000000 000000 000000 000000 000000 000000 000000
111111 111111 111111 111111 111111 111111 111111 111111 111111
u1
u2
u3 B
C D
- +
z
A E
F
1 1
2 3 4 5 6
2 3 4
u′4
S
ott= {E}, E = (1, 10/3)
U (P
1) = 11
Rilassamento lineare di P 2
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000
11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111
u1
u2 A
B
C D
- +
z
H
Gu′′4 u3
1 1
2 3 4 5 6
2 3 4
S
ott= {H}, H = (2, 45/14)
U (P
2) = 163/14
Albero di branch-and-bound
"
"
"
"
Q Q
Q Q
x1 ≤ 1 x1 ≥ 2 P0
P1 P2 U(P2) = 16314 LB = −∞
U(P1) = 11
Ulteriore suddivisione
Dopo aver suddiviso il problema P
0nei due sottoproblemi P
1e P
2, possiamo selezionare uno dei due sottoproblemi.
Quale nodo selezionare?
Diverse regole possibili. Qui ne vedremo una soltanto:
seleziona un sottoproblema/nodo foglia con upper bound massimo.
Perché? Ci si aspetta di trovare piú facilmente la soluzione
ottima del problema in un sottoproblema con un valore di
upper bound elevato.
Nell’esempio
Nel nostro esempio selezioniamo P
2.
P
2suddiviso in due sottoproblemi P
3e P
4. Come?
Esattamente come abbiamo fatto per P
0: facendo
branching su una variabile con valore non intero nella
soluzione ottima del rilassamento lineare di P
2.
Il sottoproblema P 3
P
3: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′′4) x
1≥ 2
(u
′5) x
2≤ 45 14
= 3 x
1, x
2≥ 0
x
1, x
2∈ I
Il sottoproblema P 4
P
4: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′′4) x
1≥ 2
(u
′′5) x
2≥ 45 14
+ 1 = 4 x
1, x
2≥ 0
x
1, x
2∈ I
Il rilassamento lineare di P 3
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000
11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111 11111111111111111111111
u1
u2 A
B
C D
- +
z
G
u′5 H
J K
u3 u′′4
1 1
2 3 4 5 6
2 3 4
S
ott= {J} , J = (23/10, 3)
U (P
3) = 113/10
Il rilassamento lineare di P 4
u1
u3 A
B
C D
- +
z u′′4
H
G
u2 u′′5
1 1
2 3 4 5 6
2 3 4
S
a= ∅ , quindi P
4é risolto → P
4ha regione ammissibile
vuota.
Albero di branch-and-bound
"
"
"
"
Q Q
Q Q
PPP PP
QQ QQ
x1 ≤ 1 x1 ≥ 2 P0
P1 P2
LB = −∞
P3 P4
U(P3) = 11310
x2 ≤ 3 x2 ≥ 4 U(P1) = 11
Continua
Al momento: il problema iniziale P
0é suddiviso in tre sottoproblemi P
1, P
3, P
4, di cui P
4é giá risolto
(cancellazione del nodo nell’albero).
Ora: seleziono il nodo foglia/sottoproblema non ancora
cancellato con upper bound maggiore (nell’esempio P
3) e lo
suddivido in due sottoproblemi (nell’esempio P
5e P
6).
Il sottoproblema P 5
P
5: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′′4) x
1≥ 2
(u
′5) x
2≤ 3 (u
′6) x
1≤ 23
10
= 2
x
1, x
2≥ 0
Il sottoproblema P 6
P
6: max x
1+ 3x
2(u
1) x
1≥ 1 2
(u
2) −5x
1+ 3x
2≤ 5 (u
3) x
1+ 7
5 x
2≤ 13 2 (u
′′4) x
1≥ 2
(u
′5) x
2≤ 3 (u
′′6) x
1≥ 23
10
+ 1 = 3
x , x ≥ 0
Il rilassamento lineare di P 5
u1
u2
u3 A
B
C D
- +
z u′′4
G
u′5 H
J
u′6 K
1 1
2 3 4 5 6
2 3 4
S
ott= {K} , K = (2, 3) : coordinate intere, quindi K risolve anche P
5! Valore ottimo di P
5= 11
Posso aggiornare LB → LB = 11
Il rilassamento lineare di P 6
000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000000
111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111 111111111111111111
u1
u2 A
B
C D
- +
z u′′4
G
u′5 H
J K
L
uM′′6 u3
1 1
2 3 4 5 6
2 3 4
S
ott= {L} , L = (3, 5/2)
U (P
6) = 21/2
Cancellazione nodi
Oltre ai nodi/sottoproblemi “risolti”, posso anche cancellare nodi foglia/sottoproblemi “non risolti”:
cancella un nodo P
ise U (P
i) ≤ LB
In tal caso tutte le soluzioni in P
isono non migliori rispetto alla migliore osservata sino ad ora (valore LB ) e quindi non vale la pena esplorarle.
Nel nostro esempio, cancella P
1e P
6.
Albero di branch-and-bound
"
"
"
"
Q Q
Q Q
PPP PP
QQ QQ
! !
! !
! aa
@ aa
@ @
% %
% % bb
bb
@ @
@
% %
%
x1 ≤ 1 x1 ≥ 2 P0
P1 P2
P3 P4
P5 P6
U(P6) = 212 U(P5) = 11
LB = 11
x2 ≤ 3 x2 ≥ 4
x1 ≤ 2 x1 ≥ 3 U(P1) = 11
Regola di arresto
STOP quando tutti i nodi foglia sono stati cancellati.
Al momento dell’arresto LB restituisce il valore ottimo di P
0.
Se LB = −∞ , allora P
0ha regione ammissibile vuota.
Algoritmo generale
Inizializzazione Inizializza F (insieme nodi foglia non cancellati) con P
0, F = {P
0} . Risolvi il rilassamento lineare P
0′di P
0e sia (x
∗1(P
0), . . . , x
∗n(P
0)) la soluzione ottima trovata e U (P
0) il corrispondente valore ottimo.
Se tutti i valori x
∗i(P
0), i = 1, . . . , n sono interi, STOP: la soluzione (x
∗1(P
0), . . . , x
∗n(P
0)) é soluzione ottima anche per P
0ed il valore ottimo di P
0é pari a U (P
0) . Altrimenti si ponga LB = −∞ e si vada al Passo 1.
Passo 1 Seleziona in F un nodo Q ∈ F tale che U (Q) = max
P ∈F
