idol

Idol - un cadre C ++ pour l'optimisation

Idol est une bibliothèque C ++ pour l'optimisation mathématique et la prise de décision complexe.

Il est conçu pour vous aider à créer facilement de nouveaux algorithmes pour résoudre des problèmes de plus en plus difficiles. Il s'agit d'un outil polyvalent et puissant qui peut être utilisé pour résoudre un large éventail de problèmes d'optimisation, notamment la programmation linéaire mixte (MILP), les problèmes quadratiques contraints (MiQCQP et MIQP), les problèmes de Bilevel (BO), les problèmes d'optimisation robustes (RO et ARO) et bien d'autres.

• Documentation
• Utiliser l'idole pour la recherche?
• Exemples
  • Branche
  • Problème de Bilevel (en utilisant la pièce ou les MIB)
• Fonctionnalités implémentées
  • Branche
  • Génération de colonnes et branche et prix
  • Solveurs externes

Documentation

Visitez notre documentation en ligne.

Utiliser l'idole pour la recherche?

Si vous optez pour Idol dans l'un de votre projet de recherche et rencontrez certains problèmes, veuillez nous contacter chez Lefebvre (at) Uni-Trier.de.

Exemples

Branche

Regardez à quel point il est facile d'implémenter un algorithme de branche et de prix à l'aide d'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();

Problème de Bilevel (en utilisant des MIB)

Ici, Idol utilise la pièce externe Solver-OR-OR / MIBS pour résoudre un problème d'optimisation de Bilevel avec un niveau inférieur entier.

 /*
 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;

L'idole peut également être interfacée avec Root pour surveiller la progression de votre algorithme. Par exemple, voici une capture d'écran de la surveillance des MIB pour une instance de Bilevel.

Fonctionnalités implémentées

Optimisation de mixtes

Solveurs externes

Idol peut être utilisé comme interface unifiée à plusieurs solveurs open-source ou commerciaux comme

• Gurobi
• Mosek
• Glpk
• Hauts
• COIN-Or / OSI -> CPLEX, Symphonie, CBC

Branche

• Règles de sélection des nœuds: Meilleurs liés, pire liés, profondeur d'abord, meilleure estimation, largeur d'abord.
• Règles de ramification (pour la ramification variable): pseudo-coût, ramification forte (avec phases), la plus inffainible, la moins irréalisable, d'abord trouvée, uniformément aléatoire.
• Exploration de sous-marins
• Heuristique (pour la branche variable): Arrondi simple, quartier forcé détendu, branche locale
• Rappels: coupes utilisateur, coupes paresseuses

Génération de colonnes et branche et prix

• Reformulation automatique de Dantzig-Wolfe
• Ramification douce et dure disponible (c'est-à-dire la branche sur maître ou sous-problème)
• Stabilisation par lissage à double prix: Wenges (1997), Neame (2000)
• Peut résoudre des sous-problèmes en parallèle
• Soutient les prix des tarifs
• Heuristique: maître entier

Optimisation de Bilevel

• L'idol peut résoudre des problèmes optimistes à bilan mixtes à l'aide de la pièce ou des MIB du solveur externe.

Optimisation robuste en deux étapes

Génération de colonnes et de construction (CCG)

• Implémentation générique de l'algorithme CCG pour les problèmes d'optimisation robuste réglables.
• Confiance la stabilisation de la région pour les problèmes avec les décisions binaires de la première étape.
• Problème de séparation (max-min) résolu par un solveur à bilemers.

Référence

• Une référence pour l'implémentation de la branche et du prix est disponible pour le problème d'attribution généralisé.
• Une référence pour l'implémentation de branche et liée est disponible pour le problème de sac à dos.

Il s'agit d'un profil de performance calculé selon Dolan, E., Moré, J. Mathématiques. Programme. 91, 201-213 (2002) https://doi.org/10.1007/s101070100263.

Divers

Versionning est conforme à la version sémantique 2.0.0.