Branch-and-Bound

4.5 Branch-and-Bound¶

O objetivo desta técnica de projeto de algoritmos é ser capaz de melhorar (não assintoticamente) um algoritmo de backtracking em relação a tempo e para problemas de otimização. Por ser de otimização, as soluções para uma instância podem ser classificadas em: factíveis sse ela não viola nenhuma das restrições do problema; e ótimas sse são factíveis e também de melhor qualidade em relação à função objetivo. Em linhas gerais, a ideia será a de explorar a árvore do espaço de busca de maneira a podar o máximo de nós. Para isso, um algoritmo de branch-and-bound precisa manter a seguinte informação:

• Melhor solução: o custo da melhor solução observada até então;

• Potencial de um nó: para cada nó, precisamos de uma forma de determinar o quão boa a solução obtida a partir dali pode se tornar;

Observe que o potencial de um nó não representa necessariamente que existirá uma solução a partir daquele nó que tem o custo do potencial – apenas significa que não tem como obter melhor solução do que aquilo a partir dali. Outra observação é que a noção do que é melhor ou pior depende de ser um problema de maximização ou minimização: para minimização o potencial é um limite inferior, para maximização o potencial é um limite superior.

Com isso, um algoritmo de branch-and-bound pode podar um nó de um espaço de busca sempre que:

1. O nó representar uma solução não factível;

2. O nó representa um ponto onde nenhuma escolha pode ser feita, isto é, a solução candidata está completa;

3. O potencial de um nó não é melhor do que a melhor solução observada até então.

Para que essa estratégia tenha vantagens em relação ao bactracking, precisamos então sempre manter os nós ativos da árvore de busca a todo momento para então sempre escolher expandir o nó de melhor potencial (best first). Nós ativos são aqueles nós folha que ainda não foram podados.

BRANCH-AND-BOUND(b)
S* <- NIL                         # best solution found so far
N  <- { ∅ }                        # set of active nodes (partial solutions)
while N != ∅:
  choose S in N with best potential b(S)
  for each feasible item i from S:
    S' <- S ∪ {i}                  # new node
    if S' cannot be expanded:     # solution complete
      if S* == NIL or b(S') better than b(S*):
        S* <- S'
        remove from N every node S'' such that b(S'') is worse than b(S*)
    else:
      N <- N ∪ {S'}
return S*

4.5.1 Problema da mochila¶

Limite superior para o custo de soluções parciais: o potencial máximo de ganho a partir da escolha de alguns itens. Considerando $v'$ e $w'$ como sendo o que se tem de custo e benefício em um dado momento: $ub = v' + (W − w')(v_{i+1}/w_{i+1})$, isto é, o benefício que já temos mais o máximo de custo benefício para cada unidade de peso restante da mochila.

KNAPSACK-BRANCH-AND-BOUND(S, v', w', i)   # assume w, v, W are inputs to the problem
1.  if current solution is infeasible:
2.    return solution indicating worst possible potential
3.  if all items have been considered:
4.    return current solution
5.  generate two partial solutions:
6.    S_incl <- S ∪ {i}      # add item i
7.    S_excl <- S            # do not add item i
8.  determine v', w' and ub for S_incl and S_excl
9.  let A be the node with greater potential (higher ub)
10. let B be the node with lower potential (lower ub)
11. solA <- KNAPSACK-BRANCH-AND-BOUND(A, v'_A, w'_A, i+1)
12. if ub(B) <= value(solA):
13.   return solA
14. else:
15.   solB <- KNAPSACK-BRANCH-AND-BOUND(B, v'_B, w'_B, i+1)
16.   return the better of solA and solB

4.5.2 Problema da alocação¶

O problema da alocação recebe como entrada um conjunto de trabalhadores $w_1, w_2, · · · , w_n$, um conjunto de tarefas $t_1, t_2, · · · , t_n$ e um custo $c_{ij}$ para cada alocação $w_i \to t_j$ . Uma tarefa só pode ser atribuída a um único trabalhador e vice versa. O objetivo é encontrar o conjunto de $n$ alocações que minimize a soma dos custos. Vamos representar uma instância do problema como uma matriz $n × n$ onde linhas representam os trabalhadores e colunas representam as tarefas. Por exemplo:

Veja que agora o objetivo é encontrar, para cada linha, uma coluna não escolhida por nenhuma outra linha.