Filial e limite

Branch and Bound ( BB , B&B ou BnB ) é um método para resolver problemas de otimização dividindo-os em subproblemas menores e usando uma função delimitadora para eliminar subproblemas que não podem conter a solução ideal. É um paradigma de projeto de algoritmo para problemas de otimização discreta e combinatória , bem como otimização matemática . Um algoritmo branch-and-bound consiste em uma enumeração sistemática de soluções candidatas por meio de busca no espaço de estados : o conjunto de soluções candidatas é pensado como formando uma árvore enraizada com o conjunto completo na raiz. O algoritmo explora ramos desta árvore, que representam subconjuntos do conjunto solução. Antes de enumerar as soluções candidatas de um ramo, o ramo é verificado em relação aos limites estimados superior e inferior da solução ótima e é descartado se não puder produzir uma solução melhor do que a melhor encontrada até agora pelo algoritmo.

O algoritmo depende da estimativa eficiente dos limites inferior e superior das regiões/ramos do espaço de busca. Se nenhum limite estiver disponível, o algoritmo degenera para uma busca exaustiva.

O método foi proposto pela primeira vez por Ailsa Land e Alison Doig enquanto realizavam pesquisas na London School of Economics patrocinada pela British Petroleum em 1960 para programação discreta , [1] [2] e se tornou a ferramenta mais comumente usada para resolver problemas NP-difíceis. problemas de otimização. [3] O nome "branch and bind" ocorreu pela primeira vez no trabalho de Little et al. sobre o problema do caixeiro viajante . [4] [5]

Visão geral

O objetivo de um algoritmo branch-and-bound é encontrar um valor x que maximize ou minimize o valor de uma função de valor real f ( x ) , chamada de função objetivo, entre algum conjunto S de soluções admissíveis ou candidatas . O conjunto S é chamado de espaço de busca ou região viável . O restante desta seção assume que a minimização de f ( x ) é desejada; esta suposição vem sem perda de generalidade , uma vez que pode-se encontrar o valor máximo de f ( x ) encontrando o mínimo de g ( x ) = − f ( x ) . Um algoritmo B&B opera de acordo com dois princípios:

  • Ele divide recursivamente o espaço de busca em espaços menores, minimizando então f ( x ) nesses espaços menores; a divisão é chamada de ramificação .
  • A ramificação por si só equivaleria à enumeração de força bruta de soluções candidatas e ao teste de todas elas. Para melhorar o desempenho da busca por força bruta, um algoritmo B&B rastreia os limites do mínimo que está tentando encontrar e usa esses limites para " podar " o espaço de busca, eliminando soluções candidatas que ele pode provar que não conterão. uma solução ótima.

Transformar esses princípios em um algoritmo concreto para um problema de otimização específico requer algum tipo de estrutura de dados que represente conjuntos de soluções candidatas. Tal representação é chamada de instância do problema. Denote o conjunto de soluções candidatas de uma instância I por S I . A representação da instância deve vir com três operações:

  • branch( I ) produz duas ou mais instâncias, cada uma representando um subconjunto de S I . (Normalmente, os subconjuntos são disjuntos para evitar que o algoritmo visite a mesma solução candidata duas vezes, mas isso não é obrigatório. No entanto, uma solução ótima entre SI deve estar contida em pelo menos um dos subconjuntos. [6] )
  • bind( I ) calcula um limite inferior no valor de qualquer solução candidata no espaço representado por I , ou seja, bind( I ) ≤ f ( x ) para todo x em S I .
  • solução( I ) determina se I representa uma única solução candidata. (Opcionalmente, se isso não acontecer, a operação pode optar por retornar alguma solução viável dentre SI . [6] ) Se solução( I ) retornar uma solução então f (solução( I ) ) fornece um limite superior para o objetivo ideal valor sobre todo o espaço de soluções viáveis.

Usando essas operações, um algoritmo B&B realiza uma busca recursiva de cima para baixo na árvore de instâncias formada pela operação de ramificação. Ao visitar uma instância I , ele verifica se bind( I ) é igual ou maior que o limite superior atual; nesse caso, posso ser descartado com segurança da pesquisa e a recursão é interrompida. Esta etapa de remoção geralmente é implementada mantendo uma variável global que registra o limite superior mínimo visto entre todas as instâncias examinadas até agora.

Versão genérica

A seguir está o esqueleto de um algoritmo genérico de ramificação e limite para minimizar uma função objetivo arbitrária f . [3] Para obter um algoritmo real a partir disso, é necessária uma função delimitadora bind , que calcula os limites inferiores de f nos nós da árvore de pesquisa, bem como uma regra de ramificação específica do problema. Como tal, o algoritmo genérico apresentado aqui é uma função de ordem superior .

  1. Usando uma heurística , encontre uma solução x h para o problema de otimização. Armazene seu valor, B = f ( x h ) . (Se nenhuma heurística estiver disponível, defina B como infinito.) B denotará a melhor solução encontrada até agora e será usado como limite superior nas soluções candidatas.
  2. Inicialize uma fila para manter uma solução parcial sem nenhuma das variáveis ​​do problema atribuída.
  3. Faça um loop até que a fila esteja vazia:
    1. Retire um nó N da fila.
    2. Se N representa uma única solução candidata x e f ( x ) < B , então x é a melhor solução até agora. Grave e defina Bf ( x ) .
    3. Caso contrário, ramifique N para produzir novos nós N i . Para cada um deles:
      1. Se vinculado( N i ) > B , não faça nada; como o limite inferior neste nó é maior que o limite superior do problema, ele nunca levará à solução ótima e poderá ser descartado.
      2. Caso contrário, armazene N i na fila.

Várias estruturas de dados de fila diferentes podem ser usadas. Essa implementação baseada na fila FIFO produz uma pesquisa ampla . Uma pilha (fila LIFO) produzirá um algoritmo de profundidade . Um algoritmo de melhor ramificação e limite pode ser obtido usando uma fila de prioridade que classifica os nós em seu limite inferior. [3] Exemplos de algoritmos de busca do melhor primeiro com esta premissa são o algoritmo de Dijkstra e sua busca descendente A* . A variante em profundidade é recomendada quando nenhuma boa heurística está disponível para produzir uma solução inicial, porque produz rapidamente soluções completas e, portanto, limites superiores. [7]

Pseudo-código

Uma implementação de pseudocódigo semelhante ao C++ acima é:

// Implementação semelhante a C++ de branch and bind,
// assumindo que a função objetivo f deve ser minimizada
Solução Combinatória branch_and_bound_solve ( 
    Problema de problema combinatório ,  
    Função Objetivo função_objetivo /*f*/ ,  
    BoundingFunction lower_bound_function /*bound*/ )   
{
    // Passo 1 acima
    duplo problema_upper_bound = std :: limites_numéricos < duplo > :: infinito ; //= B    
    Solução Combinatorial heurística_solução = solução_heurística ( problema ); //x_h    
    problema_upper_bound = função_objetivo ( solução_heurística ); // B = f(x_h)   
    Solução Combinatorial current_optimum = solução_heurística ;   
    // Passo 2 acima
    fila < CandidateSolutionTree > candidate_queue ; 
    // inicialização da fila específica do problema
    candidate_queue = populate_candidates ( problema );  
    while ( ! candidate_queue . vazio ()) { // Etapa 3 acima   
        // Etapa 3.1
        CandidateSolutionTree = candidate_queue . pop ();   
        // "nó" representa N acima
        if ( node.representa_single_candidate ( )) { // Etapa 3.2   
            if ( objetivo_função ( . candidato ()) < problema_superior_bound ) {    
                current_optimum = . candidato ();  
                problema_upper_bound = função_objetivo ( atual_optimum );  
            }
            // caso contrário, o nó é um único candidato que não é o ideal
        }
        else { // Etapa 3.3: o nó representa um ramo de soluções candidatas  
            // "child_branch" representa N_i acima
            for ( auto && filho_branch : . candidatos_nodes ) {     
                if ( função_limite_inferior ( filho_branch ) <= problema_limite_superior ) {    
                    fila_candidata . enfileirar ( filho_branch ); // Etapa 3.3.2 
                }
                // caso contrário, bind(N_i) > B então podamos o galho; passo 3.3.1
            }
        }
    }
    retornar atual_ótimo ; 
}

No pseudocódigo acima, as funções heuristic_solvee populate_candidateschamadas como sub-rotinas devem ser fornecidas conforme aplicável ao problema. As funções f ( objective_function) e bind ( lower_bound_function) são tratadas como objetos de função conforme escritas, e podem corresponder a expressões lambda , ponteiros de função e outros tipos de objetos que podem ser chamados na linguagem de programação C++.

Melhorias

Quando é um vetor de , algoritmos de ramificação e limite podem ser combinados com análise de intervalo [8] e técnicas de contratante para fornecer fechamentos garantidos do mínimo global. [9] [10]

Formulários

Esta abordagem é usada para vários problemas NP-difíceis :

Branch-and-bound também pode ser a base de várias heurísticas . Por exemplo, pode-se desejar parar a ramificação quando o intervalo entre os limites superior e inferior se tornar menor que um determinado limite. Isto é usado quando a solução é "boa o suficiente para fins práticos" e pode reduzir bastante os cálculos necessários. Este tipo de solução é particularmente aplicável quando a função de custo utilizada é ruidosa ou é o resultado de estimativas estatísticas e, portanto, não é conhecida com precisão, mas apenas se sabe que está dentro de um intervalo de valores com uma probabilidade específica . [ carece de fontes ]

Relação com outros algoritmos

Nau et al. apresentam uma generalização de ramificação e limite que também inclui os algoritmos de busca A* , B* e alfa-beta . [16]

Exemplo de otimização

Branch and Bound pode ser usado para resolver este problema

Maximize com essas restrições

e são inteiros.

O primeiro passo é relaxar a restrição de número inteiro. Temos dois pontos extremos para a primeira equação que formam uma reta: e . Podemos formar a segunda linha com os pontos vetoriais e .

as duas linhas.

O terceiro ponto é . Esta é uma região de casco convexa , portanto a solução está em um dos vértices da região. Podemos encontrar a interseção usando redução de linha, que é , ou com um valor de 276,667. Testamos os outros pontos finais varrendo a linha sobre a região e descobrimos que este é o máximo sobre os reais.

Escolhemos a variável com a parte fracionária máxima, neste caso passa a ser o parâmetro para o método branch andbound. Nós ramificamos e obtemos 276 @ . Alcançamos uma solução inteira, então passamos para o outro ramo . Obtemos 275,75 @ . Temos um decimal, então ramificamos e encontramos 274.571 @ . Tentamos o outro ramo e não há soluções viáveis. Portanto, o máximo é 276 com e .

Veja também

Referências

  1. ^ AH Terra e AG Doig (1960). “Um método automático para resolver problemas de programação discreta”. Econométrica . 28 (3): 497–520. doi :10.2307/1910129. JSTOR  1910129.
  2. ^ "Notícias da equipe" . www.lse.ac.uk. ​Arquivado do original em 24/02/2021 . Recuperado em 08/10/2018 .
  3. ^ Clausen, Jens (1999). Algoritmos Branch and Bound - Princípios e Exemplos (PDF) (Relatório técnico). Universidade de Copenhague . Arquivado do original (PDF) em 23/09/2015 . Recuperado em 13/08/2014 .
  4. ^ ab Pouco, John DC; Murty, Katta G.; Sweeney, Dura W.; Karel, Carolina (1963). "Um algoritmo para o problema do caixeiro viajante" (PDF) . Pesquisa Operacional . 11 (6): 972–989. doi :10.1287/opre.11.6.972. hdl : 1721.1/46828 .
  5. ^ Balas, Egon; TOTH, Paulo (1983). Métodos de ramificação e limite para o problema do caixeiro viajante (PDF) (Relatório). Escola de Pós-Graduação em Administração Industrial da Carnegie Mellon University . Arquivado (PDF) do original em 20 de outubro de 2012.
  6. ^ Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Projeto de algoritmo paralelo para ramificação e limite" (PDF) . Em Greenberg, HJ (ed.). Tutoriais sobre Metodologias Emergentes e Aplicações em Pesquisa Operacional . Imprensa Acadêmica Kluwer. Arquivado do original (PDF) em 13/08/2017 . Recuperado em 16/09/2015 .
  7. ^ Mehlhorn, Kurt ; Sanders, Pedro (2008). Algoritmos e estruturas de dados: a caixa de ferramentas básica (PDF) . Springer. pág. 249.
  8. ^ Moore, RE (1966). Análise de intervalo . Englewood Cliff, Nova Jersey: Prentice-Hall. ISBN 0-13-476853-1.
  9. ^ Jaulin, L.; Kieffer, M.; Didrit, O.; Valter, E. (2001). Análise de intervalo aplicada . Berlim: Springer. ISBN  1-85233-219-0.
  10. ^ Hansen, ER (1992). Otimização Global usando Análise de Intervalo . Nova York: Marcel Dekker.
  11. ^ Conway, Richard Walter ; Maxwell, William L .; Miller, Louis W. (2003). Teoria do Agendamento . Publicações Courier Dover. págs. 56–61.
  12. ^ Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "Um algoritmo de ramificação e limite para calcular k vizinhos mais próximos". Transações IEEE em Computadores (7): 750–753. doi :10.1109/tc.1975.224297. S2CID5941649  .
  13. ^ Narendra, Patrenahalli M.; Fukunaga, K. (1977). "Um algoritmo de ramificação e limite para seleção de subconjunto de recursos" (PDF) . Transações IEEE em computadores . C-26 (9): 917–922. doi :10.1109/TC.1977.1674939. S2CID26204315  .
  14. ^ Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali (2020). "Regressão esparsa em escala: ramificação e limite enraizada na otimização de primeira ordem". arXiv : 2004.06152 [stat.CO].
  15. ^ Nowozin, Sebastião; Lampert, Christoph H. (2011). "Aprendizagem Estruturada e Predição em Visão Computacional". Fundamentos e Tendências em Computação Gráfica e Visão . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . doi :10.1561/0600000033. ISBN  978-1-60198-457-9.
  16. ^ Nau, Dana S.; Kumar, Vipin; Canal, Laveen (1984). "Ramo e limite geral e sua relação com A∗ e AO∗" (PDF) . Inteligência artificial . 23 (1): 29–58. doi :10.1016/0004-3702(84)90004-3.

links externos

  • LiPS – Programa GUI gratuito e fácil de usar, destinado a resolver problemas de programação linear, inteira e de metas.
  • Cbc – (Coin-or branch and cut) é um solucionador de programação inteira mista de código aberto escrito em C++.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Branch_and_bound&oldid=1192337651"