6. Problemas Clássicos
- Quais problemas são classicamente resolvidos com Branch & Bound
- Por que esses problemas se encaixam no modelo de Branch & Bound
- Como branching, bounding e pruning aparecem em cada caso
- O que torna alguns problemas mais difíceis que outros
- Como o framework se adapta a diferentes cenários de otimização
Branch & Bound não está associado a um único problema. Ele é um framework geral que se aplica sempre que temos:
- um espaço de busca combinatório,
- uma função objetivo,
- e limites úteis para poda.
Nesta parte, examinamos os problemas clássicos onde Branch & Bound é mais estudado e aplicado.
6.1 Mochila 0/1
O problema da Mochila 0/1 é um dos exemplos mais clássicos de Branch & Bound.
Cada item pode ser:
- incluído, ou
- excluído.
Isso naturalmente gera uma árvore de busca binária.
Um limite comum é obtido a partir da relaxação da mochila fracionária, onde os itens podem ser escolhidos parcialmente.
6.2 Problema do Caixeiro Viajante (TSP)
No Problema do Caixeiro Viajante, o objetivo é encontrar o ciclo Hamiltoniano mais curto visitando cada cidade exatamente uma vez.
Branch & Bound é frequentemente usado explorando tours parciais e podando aqueles que não podem levar a uma solução ótima completa.
Limites típicos podem vir de:
- estimativas de arestas mínimas,
- matrizes de custo reduzido,
- ou relaxações como limites baseados em assignment.
O TSP é um exemplo clássico de como bounds fortes podem reduzir drasticamente o espaço de busca.
6.3 Problemas de Atribuição
Problemas de atribuição tratam de como associar agentes a tarefas minimizando custo ou maximizando valor.
Uma solução com Branch & Bound normalmente ramifica uma decisão de atribuição por vez, enquanto o bound vem de uma versão relaxada do subproblema restante.
Esses problemas são especialmente úteis para entender como limites inferiores guiam problemas de minimização.
6.4 Problemas de Escalonamento
Muitos problemas de escalonamento também podem ser resolvidos com Branch & Bound.
Aqui, os nós normalmente representam cronogramas parciais, e o bound estima o melhor tempo de conclusão ou o menor custo restante.
Escalonamento é um bom exemplo de como o mesmo framework se adapta a restrições e objetivos específicos de domínio.
6.5 Programação Inteira
Branch & Bound é uma das técnicas fundamentais por trás dos solucionadores modernos de programação inteira.
Nesse contexto, o algoritmo ramifica sobre variáveis inteiras e utiliza relaxações de programação linear para calcular bounds.
Isso mostra o Branch & Bound em um nível mais avançado: ele se torna um mecanismo geral de otimização exata.
6.6 O padrão comum entre os problemas
Embora esses problemas pareçam diferentes na superfície, todos compartilham o mesmo padrão estrutural:
- Representar soluções parciais como nós
- Ramificar refinando uma decisão
- Calcular um bound para a melhor continuação possível
- Podar nós que não melhoram a solução atual
6.7 Por que são chamados de “problemas clássicos”
Esses exemplos são considerados clássicos porque ilustram claramente:
- a explosão combinatória,
- a necessidade de otimização exata,
- e o valor da poda inteligente.
Eles também aparecem frequentemente em livros, pesquisas em otimização e sistemas reais de engenharia.
6.8 Resumo
- Mochila é o exemplo introdutório padrão
- TSP mostra a importância de bounds fortes
- Assignment e escalonamento mostram casos de minimização
- Programação inteira revela o poder geral do framework
- As três ideias sempre aparecem: branch, bound e prune
Próximo: Parte 7 — Complexidade
Agora que vimos onde Branch & Bound é aplicado, a próxima questão é: qual o custo disso?
Na Parte 7, estudaremos a complexidade do método, incluindo o pior caso e o papel da poda na prática.