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
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
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\}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^* \rceilCada 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}}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
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
Abrir referência DOICopiado.