idol

Idol - ein C ++ - Framework zur Optimierung

Idol ist eine C ++ - Bibliothek für mathematische Optimierung und komplexe Entscheidungsfindung.

Es soll Ihnen helfen, neue Algorithmen leicht aufzubauen, um immer schwierigere Probleme zu lösen. Es ist ein vielseitiges und leistungsstarkes Tool, mit dem eine breite Palette von Optimierungsproblemen gelöst werden kann, einschließlich linearer Programmierung mit gemischtem Inspektiv (MILP), quadratisch einschränken Probleme (MIQCQP und MIQP), Bilevelvel-Probleme (BO), robuste Optimierungsprobleme (RO und ARO) und vieles mehr.

• Dokumentation
• Verwenden Sie Idol für Forschung?
• Beispiele
  • Ast-and-Price
  • BILEVEL-Problem (mit Münz- oder MIBs)
• Implementierte Funktionen
  • Zweig und gebunden
  • Spaltengenerierung und Ast-and-Price
  • Externe Löser

Dokumentation

Besuchen Sie unsere Online -Dokumentation.

Verwenden Sie Idol für Forschung?

Wenn Sie sich für Idol in einem Ihrer Forschungsprojekte entscheiden und auf einige Probleme stoßen, kontaktieren Sie uns bitte unter lefebvre (at) uni-tier.de.

Beispiele

Ast-and-Price

Schauen Sie sich an, wie einfach es ist, einen Zweig-und-Prei-Algorithmus mit IDOL zu implementieren.

 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();

Bilevel -Problem (mit MIBs)

Hier verwendet IDOL die externen Löser-Münz- oder MIBs, um ein Bilevel-Optimierungsproblem mit einer integeren niedrigeren Ebene zu lösen.

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

Idol kann auch mit Wurzel miteinander verbunden sein, um den Fortschritt Ihres Algorithmus zu überwachen. Zum Beispiel finden Sie hier einen Screenshot der Überwachung von MIBs für eine Bilevel -Instanz.

Implementierte Funktionen

Optimierung mit gemischtem Intenzern

Externe Löser

Idol kann als einheitliche Schnittstelle zu mehreren Open-Source- oder kommerziellen Löser wie verwendet werden

• Gurobi
• Mosek
• GLPK
• Höhen
• Münz- oder OSI-> Cplex, Symphonie, CBC

Zweig und gebunden

• Knotenauswahlregeln: Beste gebundene, schlimmste gebundene Tiefe zuerst, beste Schätzung, Breite zuerst.
• Verzweigungsregeln (für variable Verzweigungen): Pseudokosten, starke Verzweigung (mit Phasen), am wenigsten, am wenigsten unleichträtig, zuerst gefunden, gleichmäßig zufällig.
• Subbree -Erkundung
• Heuristik (für variable Verzweigungen): Einfache Rundung, entspannte erzwungene Nachbarschaft, lokale Verzweigung
• Rückrufe: Benutzerschnitte, faule Schnitte

Spaltengenerierung und Ast-and-Price

• Automatische Dantzig-Wolfe-Neuformulierung
• Weiche und harte Verzweigung verfügbar (dh, Verzweigung auf Master oder Unterproblem)
• Stabilisierung durch Dual -Price -Glättung: Gentes (1997), Neame (2000)
• Kann Unterprobleme parallel lösen
• Unterstützt die Preiseheuristik
• Heuristik: ganzzahliger Meister

Bilevel -Optimierung

• Idol kann optimistische Bilevel-Probleme mit gemischtem Intenzern unter Verwendung der externen Lösungsmünzen-oder-MIBs lösen.

Zweistufige robuste Optimierung

Säulen- und Konstruktionsgenerierung (CCG)

• Generische Implementierung des CCG -Algorithmus für einstellbare robuste Optimierungsprobleme.
• Stabilisierung der Vertrauensregion bei Problemen mit binären Entscheidungen im ersten Stadium.
• Trennungsproblem (max-min) durch einen Bilevel-Löser gelöst.

Benchmark

• Für das verallgemeinerte Zuordnungsproblem steht ein Benchmark für die Implementierung von Zweig-und Preiserwaren zur Verfügung.
• Für das Problem der Rucksack steht ein Benchmark für die Implementierung der Zweig-und-gebundenen Implementierung zur Verfügung.

Dies ist ein Leistungsprofil, das nach Dolan, E., Moré, J. Benchmarking -Optimierungssoftware mit Leistungsprofilen berechnet wurde. Mathe. Programm. 91, 201–213 (2002) https://doi.org/10.1007/s101070100263.

Verschiedenes

Versioning entspricht der semantischen Versions 2.0.0.