Ramificação e limite - Branch and bound

Branch and bound ( BB , B&B ou BnB ) é 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 pesquisa 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 de soluções. Antes de enumerar as soluções candidatas de uma ramificação, a ramificação é verificada em relação aos limites estimados superior e inferior da solução ótima e é descartada 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 pesquisa exaustiva.

O método foi proposto pela primeira vez por Ailsa Land e Alison Doig durante a pesquisa na London School of Economics patrocinada pela British Petroleum em 1960 para programação discreta , e se tornou a ferramenta mais comumente usada para resolver problemas de otimização NP-hard . O nome "branch and bound" ocorreu pela primeira vez no trabalho de Little et al. sobre o problema do caixeiro viajante .

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 é denominado 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 de 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 .
  • Só a ramificação equivaleria a uma enumeração de força bruta de soluções candidatas e testá-las todas. Para melhorar o desempenho da pesquisa de força bruta, um algoritmo de B&B mantém o controle dos limites no mínimo que está tentando encontrar e usa esses limites para " podar " o espaço de pesquisa, eliminando soluções candidatas que pode provar não conter 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. Essa representação é chamada de instância do problema. Denotam o conjunto de soluções de candidatos de uma instância eu por S eu . A representação da instância deve vir com três operações:

  • ramo ( I ) produz dois ou mais casos que representam cada um, um subconjunto de S eu . (Normalmente, os subconjuntos são separados para evitar que o algoritmo visite a mesma solução candidata duas vezes, mas isso não é necessário. No entanto, uma solução ótima entre S I deve estar contida em pelo menos um dos subconjuntos.)
  • ligado ( I ) calcula um limite inferior sobre o valor de qualquer solução candidato no espaço representada por I , isto é, ligado ( I ) ≤ f ( x ) para todos os x em S eu .
  • a solução ( I ) determina se I representa uma única solução candidata. (Opcionalmente, se não o fizer, a operação pode escolher retornar alguma solução viável dentre S I. ) Se a solução ( I ) retornar uma solução, então f (solução ( I )) fornece um limite superior para o valor objetivo ideal sobre o todo o espaço de soluções viáveis.

Usando essas operações, um algoritmo B&B realiza uma pesquisa recursiva de cima para baixo na árvore de instâncias formadas pela operação de ramificação. Ao visitar uma instância I , ele verifica se o limite ( I ) é maior do que um limite superior encontrado até agora; em caso afirmativo, posso ser descartado com segurança da pesquisa e a recursão é interrompida. Essa 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 de ramificação e limite genérico para minimizar uma função objetivo arbitrária f . Para obter um algoritmo real a partir deste, um requer uma função delimitadora vinculados , que calcula reduzir limites da f nos nós da árvore de busca, bem como uma regra de ramificação específica de problemas. 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 para infinito.) B denotará a melhor solução encontrada até agora e será usado como um limite superior nas soluções candidatas.
  2. Inicialize uma fila para manter uma solução parcial sem nenhuma das variáveis ​​do problema atribuídas.
  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-o e defina Bf ( x ) .
    3. Caso contrário, ramifique em N para produzir novos nós N i . Para cada um destes:
      1. Se vinculado ( N i )> B , não faça nada; uma vez que o limite inferior neste nó é maior do que o limite superior do problema, ele nunca levará à solução ótima e pode ser descartado.
      2. Caso contrário, armazene N i na fila.

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

Pseudo-código

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

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}

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 bound ( lower_bound_function) são tratadas como objetos de função conforme escritas e podem corresponder a expressões lambda , ponteiros de função ou functores na linguagem de programação C ++, entre outros tipos de objetos que podem ser chamados .

Melhorias

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

Formulários

Esta abordagem é usada para uma série de problemas NP-difíceis :

Branch-and-bound também pode ser uma base de várias heurísticas . Por exemplo, pode-se desejar interromper a ramificação quando a lacuna entre os limites superior e inferior se tornar menor do que um certo limite. Isso é usado quando a solução é "boa o suficiente para fins práticos" e pode reduzir muito os cálculos necessários. Este tipo de solução é particularmente aplicável quando a função de custo usada é ruidosa ou é o resultado de estimativas estatísticas e, portanto, não é conhecida com precisão, mas apenas conhecida por estar dentro de uma faixa de valores com uma probabilidade específica .

Relação com outros algoritmos

Nau et al. apresentam uma generalização de branch and bound que também inclui os algoritmos de pesquisa A * , B * e alfa-beta .

Veja também

Referências

links externos

  • LiPS - Programa GUI gratuito e fácil de usar, destinado à solução de problemas de programação lineares, inteiros e de metas.
  • Cbc - (Coin-or branch and cut) é um solucionador de programação inteira mista de código aberto escrito em C ++.