Método Branch-and-Bound

Método Branch-and-Bound (do inglês Branch and Bound, abreviado como B&B ou BnB) é um paradigma geral para a construção de algoritmos exatos para resolver problemas de otimização discreta e combinatória, em particular problemas NP-difíceis. O método representa uma estratégia de enumeração direcionada, na qual todo o conjunto de soluções viáveis é sucessivamente dividido em subconjuntos (ramificação), e para cada um deles são calculadas estimativas (limites) do valor da função objetivo. Essas estimativas permitem descartar (podar) os subconjuntos que comprovadamente não contêm soluções ótimas, o que reduz significativamente o espaço de busca.

O método foi proposto pela primeira vez por A. H. Land e A. G. Doig em 1960 para resolver problemas de programação inteira. Desde então, tornou-se uma das abordagens mais fundamentais em pesquisa operacional e ciência da computação. A característica principal do método é sua flexibilidade: não é um algoritmo específico, mas sim um esquema estratégico de alto nível (framework) adaptável à estrutura do problema a ser resolvido.

Componentes-chave do método

Na base do método estão três operações fundamentais, que são aplicadas a subconjuntos do espaço de soluções, organizados na forma de uma árvore de busca.

• Ramificação (do inglês Branching) — é o processo de divisão recursiva do conjunto atual de soluções viáveis $S_i$ em vários subconjuntos menores, geralmente disjuntos $S_{i1},S_{i2},\dots ,S_{ik}$. Cada um desses subconjuntos corresponde a um novo subproblema e é representado como um nó filho na árvore de busca. Por exemplo, em problemas de programação inteira, a ramificação é frequentemente realizada em uma variável que possui um valor fracionário na solução da relaxação de programação linear.

• Cálculo de limites (do inglês Bounding) — para cada nó da árvore de busca (ou seja, para cada subproblema), é calculada uma estimativa do valor da função objetivo. Para um problema de minimização, este é um limite inferior (lower bound), que é uma estimativa garantida por baixo para qualquer solução neste subconjunto. Na maioria das vezes, essa estimativa é obtida resolvendo-se uma relaxação do subproblema original — uma versão simplificada na qual algumas restrições complexas (por exemplo, de integralidade) são temporariamente ignoradas. A mais comum é a relaxação de programação linear (relaxação LP).

• Poda (do inglês Pruning) — é o processo de eliminar da consideração nós (e suas subárvores inteiras correspondentes) que comprovadamente não podem conter a solução ótima. Um nó é podado em um dos seguintes casos:

1. Poda por limite: O limite inferior para o nó em questão não é melhor (ou seja, é maior ou igual para um problema de minimização) do que o valor da melhor solução viável encontrada até o momento, chamada de incumbente (incumbent).
2. Poda por viabilidade: A solução da relaxação do nó é viável para o problema original (por exemplo, todas as variáveis são inteiras). Essa solução é comparada com o incumbente atual e, se for melhor, o incumbente é atualizado. Não é necessário continuar a ramificação a partir deste nó.
3. Poda por inviabilidade: O subproblema correspondente ao nó não possui soluções viáveis.

Algoritmo geral

O algoritmo geral do método Branch-and-Bound para um problema de minimização pode ser descrito pelos seguintes passos:

1. Inicialização: Encontrar uma solução viável inicial (por exemplo, usando uma heurística) e definir seu valor como o limite superior inicial (incumbente) $U$. Criar uma fila de nós ativos $Q$, contendo o nó raiz (o problema original).
2. Ciclo principal: Enquanto a fila $Q$ não estiver vazia:
   • Selecionar um nó de $Q$ de acordo com a estratégia de busca (por exemplo, busca em profundidade ou busca pela melhor avaliação).
   • Resolver a relaxação para este nó, obtendo um limite inferior $L$.
   • Podar o nó se $L\ge U$.
   • Se a solução da relaxação for viável para o problema original, atualizar o incumbente: $U\leftarrow L$.
   • Se o nó não for podado e a solução não for viável, realizar a ramificação, dividindo-o em nós filhos, e adicioná-los à fila $Q$.
3. Conclusão: Quando a fila $Q$ se torna vazia, o algoritmo termina. A solução encontrada, correspondente ao incumbente $U$, é globalmente ótima.

Propriedades e teoremas-chave

• Correção e convergência: O algoritmo garante encontrar a solução globalmente ótima em um número finito de passos, se o conjunto de soluções viáveis for finito e o procedimento de ramificação for convergente (ou seja, durante a divisão recursiva, os subconjuntos "convergem" para pontos).
• Estratégia de busca: A eficiência do algoritmo depende fortemente da estratégia de seleção do próximo nó para ramificação (por exemplo, busca em profundidade, busca em largura, busca pela melhor avaliação) e da escolha da variável para ramificação. Solucionadores modernos frequentemente usam estratégias híbridas.

Exemplos

• Problema de programação inteira: Uma aplicação clássica do método. Como relaxação, utiliza-se a programação linear. A ramificação ocorre em uma variável fracionária $x_j$, criando dois subproblemas com as restrições adicionais $x_j\le \lfloor x_j^{*}\rfloor$ e $x_j\ge \lceil x_j^{*}\rceil$.
• Problema do caixeiro-viajante: O espaço de soluções consiste em todos os possíveis ciclos hamiltonianos em um grafo. A ramificação pode ser feita por arestas (incluir/excluir uma aresta da rota). Como limites inferiores, podem ser usadas soluções de problemas mais simples, como o problema de atribuição ou a construção de uma árvore geradora mínima.

Conceitos e aplicações relacionados

• Método Branch-and-Cut: Um método híbrido que combina B&B com o método de planos de corte. Em cada nó da árvore de busca, além de resolver a relaxação, são geradas desigualdades adicionais (cortes) que fortalecem o limite inferior, resultando em uma poda mais eficiente dos ramos.
• Backtracking: O método Branch-and-Bound pode ser visto como uma generalização deste algoritmo para problemas de otimização.
• Poda alfa-beta: Uma analogia conceitual usada em árvores de jogos para podar ramos que levam a resultados comprovadamente perdedores.

Ver também

• Programação inteira
• Otimização combinatória
• Problema do caixeiro-viajante
• Problema NP-difícil
• Método simplex