Questão de Estatística — Programação Linear — FUNDATEC 2024

Método Branch-and-Bound em Programação Inteira

Gabarito: letra C. A alternativa incorreta é a que afirma que o algoritmo B&B é fundamentado na ideia de "somar para conquistar", quando, na verdade, o princípio correto é o de "dividir para conquistar" — o problema é decomposto em subproblemas menores e mais simples de resolver, não mais complexos. As demais alternativas descrevem corretamente o método.

O Branch-and-Bound (B&B) é um algoritmo clássico para resolver problemas de programação inteira, ou seja, problemas de otimização em que algumas ou todas as variáveis de decisão devem assumir valores inteiros. Diferentemente do Simplex, que trabalha com variáveis contínuas, o B&B precisa lidar com a restrição de integralidade, o que torna o espaço de soluções discreto e mais difícil de explorar.

A ideia central do método é realizar uma enumeração inteligente das soluções candidatas. Em vez de examinar todas as soluções inteiras possíveis (o que seria computacionalmente inviável para problemas grandes), o algoritmo explora apenas uma fração delas, podando ramos que não podem conter a solução ótima. Isso é feito através de dois mecanismos complementares:

• Branch (bifurcação): o problema original é particionado em subproblemas menores, criando uma árvore de enumeração. Por exemplo, se uma variável $x$ deve ser inteira e a solução relaxada (contínua) dá $x = 3{,}7$, criam-se dois ramos: um com a restrição $x \leq 3$ e outro com $x \geq 4$.

• Bound (limite): para cada nó da árvore, calcula-se um limite (inferior ou superior) do valor da função objetivo. Se esse limite for pior que a melhor solução inteira já encontrada, o nó é podado, pois nenhuma solução naquele ramo pode ser melhor.

A alternativa C erra ao inverter o princípio: o B&B usa a estratégia de "dividir para conquistar" (decompor o problema em partes menores e mais simples), não "somar para conquistar". Além disso, a alternativa afirma que os subproblemas são "mais complexos", quando na verdade são mais simples, pois têm restrições adicionais que reduzem o espaço de busca.

Alternativa A — ✅ Correta

A afirmação está correta. O B&B é, de fato, uma forma de enumeração inteligente: ele examina as soluções candidatas de maneira organizada, usando limites para descartar grandes regiões do espaço de soluções sem precisar avaliá-las individualmente. Essa é a essência do método.

Alternativa B — ✅ Correta

Correta. O algoritmo não examina todas as soluções factíveis, mas apenas uma fração delas. É exatamente isso que o torna eficiente: a poda de ramos inviáveis ou subótimos evita a exploração exaustiva do espaço de soluções.

Alternativa C — ❌ Incorreta ⟵ GABARITO

Esta é a alternativa incorreta. O erro está em dois pontos:

1. "Somar para conquistar": o princípio correto é "dividir para conquistar" (do inglês divide and conquer). O problema é decomposto em subproblemas menores e mais simples, não "somado".

2. "Problemas menores e mais complexos": os subproblemas são menores e mais simples de resolver, pois cada bifurcação adiciona uma restrição, reduzindo o espaço de busca. A complexidade de cada subproblema individual é menor, não maior.

A banca trocou o princípio fundamental do método para confundir o candidato.

Alternativa D — ✅ Correta

Correta. A alternativa descreve com precisão a origem dos termos:

• Branch refere-se à partição do espaço de soluções em subespaços (bifurcação).

• Bound refere-se ao uso de limites calculados ao longo da enumeração para provar a otimalidade da solução e podar ramos.

Essa é a definição clássica do método.

Alternativa E — ✅ Correta

Correta. O B&B e o Simplex têm funcionamentos matemáticos distintos. O Simplex é um algoritmo iterativo para problemas de programação linear contínua, que percorre vértices da região factível. O B&B é uma estratégia de enumeração que resolve uma sequência de problemas relaxados (frequentemente usando o próprio Simplex como sub-rotina) para encontrar a solução inteira ótima. Portanto, não são idênticos.

Gabarito: letra C — a única alternativa incorreta, pois inverte o princípio fundamental do método Branch-and-Bound.