Matemática Discretapara Engenheiros

1. Modelo do Problema & Espaço de Busca

Branch & Bound costuma ser apresentado informalmente como um método que explora alternativas e descarta ramos que não podem levar à melhor resposta.

Essa intuição é útil, mas para entender a técnica com rigor, precisamos primeiro definir o modelo do problema e o espaço de busca que ela percorre.

1.1 Por que começar pelo modelo?

Branch & Bound não está ligado a um único problema específico. Ele é uma estratégia geral para resolver problemas de otimização combinatória.

Por isso, antes de discutir limites, poda ou implementação, precisamos responder:

• O que é uma solução candidata?
• Como uma solução parcial é representada?
• O que significa uma solução ser viável?
• O que exatamente queremos otimizar?

1.2 Soluções candidatas

Uma solução candidata normalmente é construída como uma sequência de decisões:

Cada variável xᵢ representa uma escolha feita no passo i, geralmente selecionada de um domínio de valores possíveis.

Uma atribuição completa pode representar uma solução final, enquanto um prefixo (x₁, …, xᵢ) representa uma solução parcial.

1.3 O espaço de busca

O conjunto de todas as soluções candidatas define o espaço de busca.

Esse espaço é naturalmente modelado como uma árvore:

• A raiz é a solução vazia
• Cada nível corresponde a uma nova decisão
• Cada aresta representa uma escolha
• Cada nó representa uma atribuição parcial

Em termos abstratos, um nó pode ser escrito como (x₁, …, xᵢ).

1.4 Viabilidade

Nem toda solução parcial deve continuar sendo explorada.

Um problema de Branch & Bound possui restrições que determinam se uma solução parcial ainda pode ser estendida até uma solução final válida.

Se a atribuição atual já viola a estrutura do problema, aquele ramo pode ser interrompido imediatamente.

1.5 Função objetivo

Diferente do backtracking clássico, em Branch & Bound não basta encontrar qualquer solução válida: queremos a melhor solução viável de acordo com uma função objetivo.

Formalmente, queremos encontrar uma solução x* tal que:

onde S é o conjunto de soluções viáveis e f(x) mede o valor da solução.

1.6 Maximização e minimização

Branch & Bound se aplica a dois grandes tipos de problema:

• Maximização: maximizar lucro, valor ou pontuação
• Minimização: minimizar custo, distância ou tempo

A estrutura da busca permanece a mesma. O que muda é como comparamos soluções e como interpretamos os limites.

1.7 Por que isso importa?

O espaço de busca costuma crescer exponencialmente com o tamanho da entrada. Um método força bruta examinaria todas as possibilidades.

Em problemas reais, isso rapidamente se torna inviável. Por isso, precisamos de uma estratégia que preserve a correção, mas reduza drasticamente a quantidade de ramos explorados.

1.8 Exemplos de problemas

Esse modelo aparece em vários problemas clássicos:

• Mochila 0/1
• Caixeiro Viajante
• Escalonamento
• Problemas de atribuição
• Programação inteira

Em todos eles, a ideia central é a mesma: construir soluções de forma incremental, avaliar viabilidade e qualidade, e evitar explorar regiões que não podem conter a solução ótima.