Skip to content
Voltar aos resultados

Branch and Bound

Proposto por
Ailsa Land & Alison Doig
Ano
1960
Tipo
Exact combinatorial optimization algorithm
Família
Mathematical programming

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Branch and Bound é um algoritmo exato sistemático para problemas de otimização combinatória e inteira, introduzido por Ailsa Land e Alison Doig em 1960.

Ele organiza o espaço de busca como uma árvore de subproblemas, usa limites superiores derivados de relaxações para podar ramos que não podem melhorar a melhor solução conhecida e garante a descoberta de uma solução inteira globalmente ótima. É a espinha dorsal dos modernos solucionadores de programação mista inteira usados em pesquisa operacional, logística, escalonamento e projeto de engenharia.

A intuição por trás do método

Imagine procurar o item de maior valor escondido em um vasto labirinto de salas. Em vez de verificar cada sala, você estima o valor máximo possível alcançável de cada corredor antes de entrar nele. Se esse teto for menor que o melhor item que você já possui, você ignora o corredor inteiro sem olhar para dentro. Branch and Bound funciona da mesma maneira: ele divide o problema em partes menores, calcula limites superiores otimistas para cada parte e descarta imediatamente qualquer parte que comprovadamente não possa superar a melhor solução atual.

História

Land e Doig publicaram o artigo fundamental sobre Branch and Bound na Econometrica em 1960, apresentando-o como um método automático para programação discreta. Little et al. (1963) aplicaram a técnica ao problema do caixeiro viajante, cimentando seu papel na otimização combinatória. Dakin (1965) introduziu a ramificação por relaxação LP, a forma mais comumente usada hoje. Décadas subsequentes viram a integração de planos de corte (branch-and-cut) e geração de colunas (branch-and-price), tornando Branch and Bound o motor por trás de todos os principais solucionadores comerciais de programação inteira.

Quando usar

Use Branch and Bound quando precisar encontrar a solução comprovadamente ótima para um programa linear misto inteiro ou puramente inteiro e não puder aceitar uma resposta aproximada. Assume que o problema pode ser formulado com relaxações lineares (ou convexas) que fornecem limites úteis. É menos adequado para instâncias muito grandes onde a árvore de enumeração explode, para programas inteiros não lineares sem relaxações apertadas, ou para cenários em tempo real onde o tempo de computação é estritamente limitado. Nesses casos, heurísticas ou metaheurísticas podem ser preferidas.

Limitações e considerações

  • A complexidade no pior caso é exponencial; em instâncias mal estruturadas, a árvore pode crescer proibitivamente grande.
  • O desempenho é altamente sensível à escolha da variável de ramificação e da estratégia de seleção de nós.
  • Requer uma relaxação tratável que forneça limites superiores significativos; limites fracos levam à poda mínima.
  • Requisitos de memória podem ser substanciais quando muitos nós abertos precisam ser armazenados simultaneamente.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Garante otimalidade global para programas inteiros e combinatórios.
  • Reduz drasticamente a busca através da poda baseada em limites — frequentemente apenas uma pequena fração da árvore de enumeração completa é explorada.
  • Flexível: pode incorporar planos de corte (branch-and-cut) ou limites heurísticos (branch-and-price) para maior eficiência.
  • Amplamente implementado em solucionadores comerciais maduros (CPLEX, Gurobi) e ferramentas de código aberto (GLPK, CBC).

Aplicações

  • Escalonamento de tripulação de companhias aéreas e atribuição de frota em pesquisa operacional.
  • Projeto de rede da cadeia de suprimentos e problemas de localização de instalações.
  • Layout de circuitos VLSI e alocação de registradores em engenharia de computação.
  • Previsão de estrutura de proteínas e montagem de genoma em biologia computacional.
  • Otimização de portfólio financeiro com restrições de cardinalidade.

Como funciona

Como funciona

1

O algoritmo começa resolvendo uma versão relaxada do problema — tipicamente a relaxação LP — que ignora as restrições de integridade. Essa relaxação produz um limite superior sobre o valor ótimo verdadeiro, pois toda solução inteira factível também é factível na relaxação. Se a solução relaxada for inteira, o problema é resolvido imediatamente.

Fórmula
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

Quando a solução relaxada contém uma variável fracionária, o algoritmo particiona a região factível adicionando restrições complementares que forçam a variável a seu piso ou teto. Cada partição cria um novo nó filho na árvore de busca, efetivamente dividindo um subproblema em dois subproblemas menores com domínios mais restritos.

Fórmula
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Cada nó ativo recebe seu próprio limite de relaxação LP. Um nó cujo limite não excede a melhor solução inteira encontrada até agora — chamada de incumbente — não pode conter uma solução melhor, portanto, é podado. Limites apertados são críticos: quanto mais apertado o limite, menos nós precisam ser explorados.

Fórmula
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Um nó é cravado (fechado permanentemente) sob três condições: sua relaxação é infactível, seu limite não é melhor que o incumbente, ou sua solução relaxada já é inteira-factível. Neste último caso, o incumbente é atualizado se a nova solução o melhorar. O algoritmo termina quando todos os nós são cravados, momento em que o incumbente é o ótimo global.

Fórmula
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Erros comuns

  • Escolher a variável de ramificação incorretamente (por exemplo, sempre ramificar na primeira variável fracionária) geralmente leva a árvores profundas e desbalanceadas e convergência lenta.
  • Ignorar desigualdades válidas (planos de corte) significa perder a oportunidade de apertar significativamente os limites de relaxação.
  • A terminação prematura com um gap de subotimalidade que não é reportado como tal pode levar os praticantes a tratar uma solução quase ótima como exata.
  • Aplicar Branch and Bound a relaxações não lineares ou não convexas sem convexificação especializada pode gerar limites inválidos e resultados incorretos.

Perguntas frequentes

Como Branch and Bound difere da enumeração exaustiva?

A enumeração exaustiva avalia explicitamente todas as soluções inteiras factíveis, o que é computacionalmente infactível para problemas grandes. Branch and Bound evita isso calculando limites superiores baseados em relaxação em cada nó da árvore de busca e podando subárvores inteiras sempre que o limite não pode exceder a melhor solução já encontrada. Na prática, apenas uma pequena fração da árvore é examinada.

Qual é o papel da relaxação LP em Branch and Bound?

A relaxação LP remove as restrições de integridade, tornando o problema solúvel em tempo polinomial pelo método simplex ou de ponto interior. Seu valor ótimo serve como um limite superior para o subproblema inteiro correspondente. Quando esse limite é apertado — próximo ao ótimo inteiro verdadeiro — menos ramos precisam ser explorados. Relaxações mais apertadas, frequentemente obtidas pela adição de desigualdades válidas, aceleram dramaticamente o algoritmo geral.

Quando devo usar Branch and Bound em vez de uma metaheurística como algoritmos genéticos?

Escolha Branch and Bound quando você requer um certificado de otimalidade e pode arcar com o tempo de computação. É ideal para problemas de médio porte com relaxações LP bem estruturadas. Metaheurísticas são preferíveis quando o problema é extremamente grande, carece de uma relaxação útil, ou deve ser resolvido dentro de um orçamento de tempo apertado onde uma solução quase ótima é aceitável. Muitos praticantes combinam ambos: usam Branch and Bound com uma tolerância de gap de terminação antecipada.

Métodos relacionados

Fontes

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    Abrir referência DOI
    Copiado.