idol

ídolo - uma estrutura C ++ para otimização

O Idol é uma biblioteca C ++ para otimização matemática e tomada de decisão complexa.

Ele foi projetado para ajudá -lo a criar novos algoritmos facilmente para resolver problemas cada vez mais desafiadores. É uma ferramenta versátil e poderosa que pode ser usada para resolver uma ampla gama de problemas de otimização, incluindo programação linear mista de Integer (MILP), problemas quadraticamente restritos (MIQCQP e MIQP), problemas de bilevel (BO), problemas de otimização robustos (RO e ARO) e muito mais.

• Documentação
• Usando o ídolo para pesquisa?
• Exemplos
  • Ramificação e preço
  • Problema de Bilevel (usando moeda-ou/mibs)
• Recursos implementados
  • Ramificação e ligação
  • Geração de colunas e ramificação e preço
  • Solucionadores externos

Documentação

Visite nossa documentação online.

Usando o ídolo para pesquisa?

Se você estiver optando pelo ídolo em um de seu projeto de pesquisa e encontrar alguns problemas, entre em contato conosco no Lefebvre (at) uni-trier.de.

Exemplos

Ramificação e preço

Veja como é fácil implementar um algoritmo de ramificação e preço usando o IDOL.

 const auto [model, decomposition] = create_model(); // Creates the model with an annotation for automatic decomposition

const auto sub_problem_specifications = 
        DantzigWolfe::SubProblem ()
          .add_optimizer(Gurobi()); // Each sub-problem will be solved by Gurobi

const auto column_generation = 
        DantzigWolfeDecomposition (decomposition)
          .with_master_optimizer(Gurobi::ContinuousRelaxation()) // The master problem will be solved by Gurobi
          .with_default_sub_problem_spec(sub_problem_specifications);

const auto branch_and_bound =
        BranchAndBound ()
          .with_node_selection_rule(BestBound()) // Nodes will be selected by the "best-bound" rule
          .with_branching_rule(MostInfeasible()) // Variables will be selected by the "most-fractional" rule
          .with_log_level(Info, Blue);

const auto branch_and_price = branch_and_bound + column_generation; // Embed the column generation in the Branch-and-Bound algorithm

model.use(branch_and_price);

model.optimize();

Problema de Bilevel (usando MIBs)

Aqui, o Idol usa a moeda de solucionador externa ou MIBS para resolver um problema de otimização de nível bilumer com nível inferior inteiro.

 /*
 This example is taken from "The Mixed Integer Linear Bilevel Programming Problem" (Moore and Bard, 1990).

    min -1 x + -10 y
    s.t.

    y in argmin { y :
        -25 x + 20 y <= 30,
        1 x + 2 y <= 10,
        2 x + -1 y <= 15,
        2 x + 10 y >= 15,
        y >= 0 and integer.
    }
    x >= 0 and integer.

 */

Env env;

// Define High Point Relaxation
Model high_point_relaxation (env);

auto x = high_point_relaxation.add_var( 0 , Inf, Integer, " x " );
auto y = high_point_relaxation.add_var( 0 , Inf, Integer, " y " );

high_point_relaxation.set_obj_expr(-x - 10 * y);
auto follower_c1 = high_point_relaxation.add_ctr(- 25 * x + 20 * y <= 30 );
auto follower_c2 = high_point_relaxation.add_ctr(x + 2 * y <= 10 );
auto follower_c3 = high_point_relaxation.add_ctr( 2 * x - y <= 15 );
auto follower_c4 = high_point_relaxation.add_ctr( 2 * x + 10 * y >= 15 );

// Prepare bilevel description
Bilevel::LowerLevelDescription description (env);
description.set_follower_obj_expr(y);
description.set_follower_var(y);
description.set_follower_ctr(follower_c1);
description.set_follower_ctr(follower_c2);
description.set_follower_ctr(follower_c3);
description.set_follower_ctr(follower_c4);

// Use coin-or/MibS as external solver
high_point_relaxation.use(Bilevel::MibS(description));

// Optimize and print solution
high_point_relaxation.optimize();

std::cout << high_point_relaxation.get_status() << std::endl;
std::cout << high_point_relaxation.get_reason() << std::endl;
std::cout << save_primal(high_point_relaxation) << std::endl;

O ídolo também pode ser interfocado com a raiz para monitorar o progresso do seu algoritmo. Por exemplo, aqui está uma captura de tela do monitoramento de MIBs para uma instância de Bilevel.

Recursos implementados

Otimização de Integer Misto

Solucionadores externos

O ídolo pode ser usado como uma interface unificada para vários solucionadores de código aberto ou comerciais, como

• Gurobi
• Mosek
• Glpk
• Elevações
• moeda-ou/osi-> CPLEX, Symphony, CBC

Ramificação e ligação

• Regras de seleção de nó: Melhor limite, pior limite, profundidade primeiro, melhor estimativa, largura primeiro.
• Regras de ramificação (para ramificação variável): custo pseudo, ramificação forte (com fases), a maioria inviável, menos inviável, encontrada pela primeira vez, uniformemente aleatória.
• Exploração da subárvore
• Heurísticas (para ramificação variável): arredondamento simples, bairro forçado descontraído, ramificação local
• Retornos de chamada: cortes de usuários, cortes preguiçosos

Geração de colunas e ramificação e preço

• Reformulação automática de Dantzig-Wolfe
• Ramificação suave e dura disponível (ou seja, ramificando-se em mestre ou subproblema)
• Estabilização por suavização de preços dupla: Wentges (1997), Neame (2000)
• Pode resolver subproblemas em paralelo
• Apoia heurísticas de preços
• Heurísticas: mestre inteiro

Otimização do Bilevel

• O Idol pode resolver problemas otimistas de bile-nível misto usando a moeda de solucionador externo ou MIBs.

Otimização robusta de dois estágios

Geração de coluna e restrição (CCG)

• Implementação genérica do algoritmo CCG para problemas de otimização robustos ajustáveis.
• Estabilização da região de confiança para problemas com decisões binárias de primeiro estágio.
• Problema de separação (MAX-MIN) resolvido por um solucionador de nível Bil.

Benchmark

• Uma referência para a implementação de ramificação e preço está disponível para o problema de atribuição generalizada.
• Uma referência para a implementação de ramificação e limite está disponível para o problema da mochila.

Este é um perfil de desempenho calculado de acordo com Dolan, E., Moré, J. Software de otimização de benchmarking com perfis de desempenho. Matemática. Programa. 91, 201–213 (2002) https://doi.org/10.1007/s101070100263.

Variado

O versão é compatível com o semântico Versionning 2.0.0.