Branch-and-Bound

A special thanks to the TA Filipe Vilas Boas for scribing this page

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.

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.

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.