Algoritmo Branch-and-Bound
Professora Adria Lyra
O algoritmo “branch-and-bound”
(B&B)
• É uma estratégia de divisão e
conquista para problemas de natureza
inteira mista
• A idéia é dividir um problema P em
um conjunto de subproblemas
menores {SPk} de forma que a
solução de P possa ser obtida através
da solução dos subproblemas.
Algoritmo Branch-and-Bound
• As divisões são feitas iterativamente,
sempre observando que os
subproblemas devem ser mais fáceis
de serem resolvidos que o problema
original.
• Além disso, procuramos descartar
subproblemas desde que estes não
contenham a solução ótima.
Estratégia de divisão e conquista
• Considere o problema:
P : z = max {cT x : x ∈ S}
• Como “quebrar” P em subproblemas
menores e depois os “recombinar”de
maneira a se obter uma solução para o
problema original?
Estratégia de divisão e conquista
• Proposição:
– Seja S = S1 ∪ . . . ∪ SK uma decomposição de S
em K conjuntos menores.
– Seja também zk = max{cT x : x ∈ Sk}
para k = 1, . . . ,K.
– Então, z = max{zk : k = 1, . . . ,K}.
• Uma estratégia de divisão e conquista,
obedecendo as premissas da proposição
acima, pode ser ilustrada com uma árvore
de enumeração.
Estratégia de divisão e conquista
• Para S ⊆ {0, 1}3, podemos construir a
árvore de enumeração abaixo.
S
x1 = 0
S0
x1= 1
S1
Estratégia de divisão e conquista
• Claramente S = S0 ∪ S1, onde
– S0 = {x ∈ S : x1 = 0} e
– S1 = {x ∈ S : x1 = 1}.
• Podemos subdividir cada um dos
subproblemas em subproblemas ainda
menores, fazendo:
– S0 = S00 ∪ S01 e
– S1 = S10 ∪ S11,
– onde Si1i2 = {x ∈ Si1 : x2 = i2}.
Estratégia de divisão e conquista
S
x1 = 0
x1= 1
S0
x2 = 0
S00
S1
x2 = 1
S01
x2 = 0
x2 = 1
S10
S11
Árvore de Enumeração
Estratégia de divisão e conquista
S
x1 = 0
x1= 1
S1
S0
x2 = 1
x2 = 0
x3 = 0
S000
S10
S01
S00
x2 = 1
x2 = 0
S11
x3 = 1
S001
S010
S011
S100
S101
S110
S111
Estratégia de divisão e conquista
• Uma folha da árvore de enumeração
completa Si1i2i3 é não-vazia se, e somente se,
x = (i1, i2, i3) ∈ S.
• Portanto, as folhas da árvore correspondem
precisamente as soluções candidatas que
seriam examinadas se fosse conduzida uma
enumeração completa.
Enumeração Implícita
• Enumeração completa é inviável para
problemas práticos
• Uma alternativa é utilizar os limites de
{zk} de forma inteligente, tanto os limites
superiores quanto os inferiores.
Enumeração Implícita
• Algoritmo Branch-and-Bound
• Proposição
– Seja S = S1 ∪ . . . ∪ Sn uma decomposição de S em n
subconjuntos.
– Seja zk = Max{cTx : x ∈ Sk} para k = 1, . . . ,n.
k
– Seja z um limite superior para zk.
k
z
– Seja
um limite inferior para zk .
• Então:
k
– z = Max{ z : k = 1, . . . ,n} define um limite superior para z
–
z
= Max{
z
k
: k = 1, . . . ,n} define um limite inferior para z
O problema da Mochila 0, 1
ub = v + (W – w)(vi+1 / wi+1)
item
1
Peso
w
4
Valor Valor/
v
peso
$40
10
2
7
$42
6
3
5
$25
5
4
3
$12
4
A
capacidade
da Mochila
é W = 10
Branch-and-Bound
W=0, v=0
Ub = 100
Com 1
Sem 1
W=4, v=40
W=0, v=0
Ub = 76
Ub = 60
Expansão da
árvore em
largura para
todos os nós
Branch-and-Bound
W=0, v=0
Ub = 119
Com 1
Com 2
W=11,
Sem 1
W=4, v=40
W=0, v=0
Ub = 76
Ub = 60
Sem 2
W=4, v=40
Ub = 70
Branch-and-Bound
W=0, v=0
ub = 119
Sem 1
Com 1
W=4, v=40
W=0, v=0
ub = 76
ub = 60
Com 2
Sem 2
W=11,
W=4, v=40
ub = 70
Com 3
Sem 3
W=9, v=65
W=4, v=40
ub = 69
ub = 64
Branch-and-Bound
W=0, v=0
ub = 119
Sem 1
Com 1
W=4, v=10
W=0, v=0
ub = 76
ub = 60
Com 2
Sem 2
W=11,
W=4, v=10
ub = 70
Sem 3
Com 3
Com 4
W=12,
W=9, v=65
W=4, v=10
ub = 69
ub = 64
Sem 4
W=9, v=65
ub = 65