Modelli e Algoritmi per la Logistica
Branch & Bound
SARA MATTIA
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Branch & Bound
min c T x

x S
z* valore ottimo
partizione di S in S1 ...Sk
Si  S j  

 S S
i
i 
1..k
z*i valore ottimo di min {c T x : x  S i }
z* = min {z*1 ... z*k }
• L lista dei sottoproblemi da esaminare
• UB upper bound per il problema
• x* soluzione corrispondente all’UB
i j
Branch & Bound
inizializzazione:
L = P, x*, UB
L=?
si
x* ottima
no
scegli Pi L
calcola LB per Pi , y
LB  UB ?
decomponi Pi
in Pi1 ...Pik
L = L  {Pi1 ...Pik}
no
no
yZ?
si
aggiorna UB e x*
si
Branch & Bound
scelta del problema:
• problema con minimo LB (best bound)
• LIFO (visita in profondità)
• FIFO (visita in ampiezza)
calcolo LB:
• Rilassamento Lineare
• Formulazione alternativa
Branch & Bound
decomposizione (branching)
• x {0,1}n
scegli xi frazionaria
• x Zn
scegli xi frazionaria
Pi0 = Pi  {xi = 0}
Pi1 = Pi  {xi = 1}
PiL  Pi  { x i  xˆi  }
PiU  Pi  { x i  xˆi  }
scelta della variabile di branching
• variabile più “intera”
• variabile più “frazionaria”
• ordine predefinito
Esempio
min 5x1  9x 2  7x 3  5x 4
4x1  5x 2  3x 3  2x 4  7

4
x

{
0
,
1
}

• soluzione del rilassamento:
r1  5 4  1,25
r2  9 5  1,8
r3  7 3  2,33
{ 1,2,3,4 }
r4  5 2  2,5
LB = 10,4
UB = 14
xˆ1  xˆ2  1

xˆ3  xˆ 4  0
xˆ1  1
xˆ 2  3 5  0,6
xˆ 3  0
xˆ 4  0
Esempio
min 5x1  9x 2  7x 3  5x 4
4x1  5x 2  3x 3  2x 4  7

4
x

{
0
,
1
}

UB = 14
xˆ1  xˆ2  1

xˆ3  xˆ 4  0
x2  0
min 5x1  7x 3  5x 4
4x1  3x 3  2x 4  7
xˆ1  1
xˆ 2  3 5  0,6
xˆ 4  0
xˆ 3  0
x2  1
9  min 5x1  7x 3  5x 4
4x1  3x 3  2x 4  2
Esempio
{ 1,2,3,4 } UB = 14
x2  0
x2  1
9  min 5x1  7x 3  5x 4
min 5x1  7x 3  5x 4
4x1  3x 3  2x 4  7
x1  0
9  min 7x 3  5x 4
3x 3  2x 4  2
xˆ1  xˆ2  1

xˆ3  xˆ 4  0
4x1  3x 3  2x 4  2
xˆ 2  1

xˆ1  1 2  0,5 LB = 11,5
xˆ  xˆ  0
4
 3
x1  1
14  min 7x 3  5x 4
3x 3  2x 4  2
LB  14 =UB
Esempio
{ 1,2,3,4 } UB = 14
x2  0
xˆ1  xˆ2  1

xˆ3  xˆ 4  0
x2  1
min 5x1  7x 3  5x 4
4x1  3x 3  2x 4  7
xˆ1  xˆ3  1

xˆ2  xˆ 4  0
LB = 12
x intera
aggiorna UB
ottima
9  min 5x1  7x 3  5x 4
4x1  3x 3  2x 4  2
x1  0
x1  1
9  min 7x 3  5x 4
14  min 7x 3  5x 4
3x 3  2x 4  2
xˆ 2  1

xˆ 3  2 3  0,66
xˆ  xˆ  0
4
 1
3x 3  2x 4  2
LB = 13,6
LB  14 = UB
Esempio
max x1  4x 2
xˆ1  2
B 
xˆ 2  3
  x1  4 x 2  5

2x1  2x 2  13

 x1  0 x 2  0
x  Z 2

LB = 11
xˆ1  4,2 UB = 13,4
A 
xˆ2  2,3
x1  4
x2
A
B
x1
1,25
1
4
5
6,5
x1
x1  5
Esempio
max x1  4x 2
LB = 11
  x1  4 x 2  5

2x1  2x 2  13

 x1  0 x 2  0
x  5
 1
x  Z 2
x
xˆ1  5
C 
xˆ2  1,5
UB = 11
2
C
1,25
1
4
5
6,5
x1
Esempio
max x1  4x 2
LB = 11
  x1  4 x 2  5

2x1  2x 2  13

 x1  0 x 2  0
x  4
 1
x  Z 2
x2
xˆ1  4
D 
xˆ 2  2,25
UB = 13
x2  2
3
x2
D
2
1,25
x2  3
1
4
5
6,5
x1
P=
Esempio
max x1  4x 2
LB = 11
  x1  4 x 2  5

2x1  2x 2  13

 x1  0 x 2  0
x  4
 1
x  Z 2
x2
xˆ1  4
E 
xˆ 2  2
UB = 12
x intera
aggiorna LB
x ottima
3
E
2
1,25
1
4
5
6,5
x1