--- title: "Método Branch-and-Bound" source: "https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound" wiki: "systems-analysis.info/int" article: "Método_Branch-and-Bound" language: "pt" categories: - "Category:Operations research" - "Category:Optimization" - "Category:Portuguese" revision_id: 4810 wiki_created_at: 2026-09-06T23:40:14Z wiki_modified_at: 2026-09-06T23:40:14Z downloaded_at: 2026-09-07T23:04:46Z --- # Método Branch-and-Bound **Método Branch-and-Bound** (do inglês *Branch and Bound*, abreviado como **B&B** ou **BnB**) é um paradigma geral para a construção de algoritmos exatos para resolver problemas de otimização discreta e combinatória, em particular problemas NP-difíceis[\[1\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-en-wiki-bnb-1). O método representa uma estratégia de enumeração direcionada, na qual todo o conjunto de soluções viáveis é sucessivamente dividido em subconjuntos (**ramificação**), e para cada um deles são calculadas estimativas (**limites**) do valor da função objetivo. Essas estimativas permitem descartar (podar) os subconjuntos que comprovadamente não contêm soluções ótimas, o que reduz significativamente o espaço de busca[\[2\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-ru-wiki-bnb-2). O método foi proposto pela primeira vez por A. H. Land e A. G. Doig em 1960 para resolver problemas de programação inteira[\[3\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-land-doig-1960-3). Desde então, tornou-se uma das abordagens mais fundamentais em pesquisa operacional e ciência da computação. A característica principal do método é sua flexibilidade: não é um algoritmo específico, mas sim um esquema estratégico de alto nível (framework) adaptável à estrutura do problema a ser resolvido. ## Componentes-chave do método Na base do método estão três operações fundamentais, que são aplicadas a subconjuntos do espaço de soluções, organizados na forma de uma árvore de busca. - **Ramificação** (do inglês *Branching*) — é o processo de divisão recursiva do conjunto atual de soluções viáveis $S_{i}$ em vários subconjuntos menores, geralmente disjuntos $S_{i1},S_{i2},\ldots,S_{ik}$. Cada um desses subconjuntos corresponde a um novo subproblema e é representado como um nó filho na árvore de busca. Por exemplo, em problemas de programação inteira, a ramificação é frequentemente realizada em uma variável que possui um valor fracionário na solução da relaxação de programação linear. - **Cálculo de limites** (do inglês *Bounding*) — para cada nó da árvore de busca (ou seja, para cada subproblema), é calculada uma estimativa do valor da função objetivo. Para um problema de minimização, este é um **limite inferior** (*lower bound*), que é uma estimativa garantida por baixo para qualquer solução neste subconjunto. Na maioria das vezes, essa estimativa é obtida resolvendo-se uma *relaxação* do subproblema original — uma versão simplificada na qual algumas restrições complexas (por exemplo, de integralidade) são temporariamente ignoradas. A mais comum é a relaxação de programação linear (relaxação LP). - **Poda** (do inglês *Pruning*) — é o processo de eliminar da consideração nós (e suas subárvores inteiras correspondentes) que comprovadamente não podem conter a solução ótima. Um nó é podado em um dos seguintes casos: 1. **Poda por limite**: O limite inferior para o nó em questão não é melhor (ou seja, é maior ou igual para um problema de minimização) do que o valor da melhor solução viável encontrada até o momento, chamada de **incumbente** (*incumbent*). 2. **Poda por viabilidade**: A solução da relaxação do nó é viável para o problema original (por exemplo, todas as variáveis são inteiras). Essa solução é comparada com o incumbente atual e, se for melhor, o incumbente é atualizado. Não é necessário continuar a ramificação a partir deste nó. 3. **Poda por inviabilidade**: O subproblema correspondente ao nó não possui soluções viáveis. ## Algoritmo geral O algoritmo geral do método Branch-and-Bound para um problema de minimização pode ser descrito pelos seguintes passos: 1. **Inicialização:** Encontrar uma solução viável inicial (por exemplo, usando uma heurística) e definir seu valor como o limite superior inicial (incumbente) $U$. Criar uma fila de nós ativos $Q$, contendo o nó raiz (o problema original). 2. **Ciclo principal:** Enquanto a fila $Q$ não estiver vazia: - Selecionar um nó de $Q$ de acordo com a estratégia de busca (por exemplo, busca em profundidade ou busca pela melhor avaliação). - Resolver a relaxação para este nó, obtendo um limite inferior $L$. - **Podar** o nó se $L \geq U$. - Se a solução da relaxação for viável para o problema original, atualizar o incumbente: $U\leftarrow L$. - Se o nó não for podado e a solução não for viável, realizar a **ramificação**, dividindo-o em nós filhos, e adicioná-los à fila $Q$. 3. **Conclusão:** Quando a fila $Q$ se torna vazia, o algoritmo termina. A solução encontrada, correspondente ao incumbente $U$, é globalmente ótima. ## Propriedades e teoremas-chave - **Correção e convergência:** O algoritmo garante encontrar a solução globalmente ótima em um número finito de passos, se o conjunto de soluções viáveis for finito e o procedimento de ramificação for convergente (ou seja, durante a divisão recursiva, os subconjuntos "convergem" para pontos)[\[4\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-conitzer-duke-4). - **Estratégia de busca:** A eficiência do algoritmo depende fortemente da estratégia de seleção do próximo nó para ramificação (por exemplo, busca em profundidade, busca em largura, busca pela melhor avaliação) e da escolha da variável para ramificação. Solucionadores modernos frequentemente usam estratégias híbridas[\[5\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-maudet-danoy-2024-5). ## Exemplos - **Problema de programação inteira**: Uma aplicação clássica do método. Como relaxação, utiliza-se a programação linear. A ramificação ocorre em uma variável fracionária $x_{j}$, criando dois subproblemas com as restrições adicionais $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ e $x_{j} \geq \lceil x_{j}^{\ast}\rceil$. - **Problema do caixeiro-viajante**: O espaço de soluções consiste em todos os possíveis ciclos hamiltonianos em um grafo. A ramificação pode ser feita por arestas (incluir/excluir uma aresta da rota). Como limites inferiores, podem ser usadas soluções de problemas mais simples, como o problema de atribuição ou a construção de uma árvore geradora mínima[\[6\]](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_note-little-1963-6). ## Conceitos e aplicações relacionados - **Método Branch-and-Cut**: Um método híbrido que combina B&B com o método de planos de corte. Em cada nó da árvore de busca, além de resolver a relaxação, são geradas desigualdades adicionais (cortes) que fortalecem o limite inferior, resultando em uma poda mais eficiente dos ramos. - **Backtracking**: O método Branch-and-Bound pode ser visto como uma generalização deste algoritmo para problemas de otimização. - **Poda alfa-beta**: Uma analogia conceitual usada em árvores de jogos para podar ramos que levam a resultados comprovadamente perdedores. ## Ver também - Programação inteira - Otimização combinatória - Problema do caixeiro-viajante - Problema NP-difícil - Método simplex ## Notas 1. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-en-wiki-bnb_1-0) Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound 2. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-ru-wiki-bnb_2-0) Wikipedia contributors. (2023). Метод ветвей и границ. In *Wikipédia em russo*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-land-doig-1960_3-0) Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. *Econometrica*, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129 4. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-conitzer-duke_4-0) Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf 5. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-maudet-danoy-2024_5-0) Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. *arXiv preprint arXiv:2412.09444*. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444 6. [↑](https://systems-analysis.info/int/M%C3%A9todo_Branch-and-Bound#cite_ref-little-1963_6-0) Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. *Operations Research*, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf