idol - The Mathematical Optimization Framework

Idol is a powerful and flexible library meticulously crafted for developing new mathematical optimization algorithms.

It is built to provide researchers with a versatile toolkit to construct, tweak, and experiment with state-of-the-art methods. Whether you're exploring Branch-and-Price, Benders decomposition, Column-and-Constraint generation for adjustable robust problems, or any other cutting-edge method, idol is your trusted companion.

Documentation
Using idol for Research?
Examples
- Branch-and-Price
- Bilevel Problem (using coin-or/Mibs)
Implemented Features

Documentation

Visit our online documentation.

Using idol for Research?

If you are opting for idol in one of your research project and encounter some issues, please contact us at lefebvre(at)uni-trier.de.

Examples

Branch-and-Price

Look at how easy it is to implement a Branch-and-Price algorithm using 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();

Bilevel Problem (using MibS)

Here, idol uses the external solver coin-or/MibS to solve a bilevel optimization problem with integer lower level.

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

Implemented Features

Mixed-Integer Optimization

External Solvers

Idol can be used as a unified interface to several open-source or commercial solvers like

Branch-and-Bound

Node selection rules: Best Bound, Worst Bound, Depth First, Best Estimate, Breadth First.
Branching rules (for variable branching): Pseudo Cost, Strong Branching (with phases), Most Infeasible, Least Infeasible, First Found, Uniformly Random.
Subtree exploration
Heuristics (for variable branching): Simple Rounding, Relaxed Enforced Neighborhood, Local Branching
Callbacks: User Cuts, Lazy Cuts

Column Generation and Branch-and-Price

Automatic Dantzig-Wolfe reformulation
Soft and hard branching available (i.e, branching on master or sub-problem)
Stabilization by dual price smoothing: Wentges (1997), Neame (2000)
Can solve sub-problems in parallel
Supports pricing heuristics
Heuristics: Integer Master

Bilevel Optimization

Idol can solve optimistic mixed-integer bilevel problems using the external solver coin-or/MibS.

Two-stage Robust Optimization

Column-and-Constraint Generation (CCG)

Generic implementation of the CCG algorithm for adjustable robust optimization problems.
Trust region stabilization for problems with binary first stage decisions.
Separation problem (max-min) solved by a bilevel solver.

Benchmark

A benchmark for the Branch-and-Price implementation is available for the Generalized Assignment Problem.
A benchmark for the Branch-and-Bound implementation is available for the Knapsack Problem.

This is a performance profile computed according to Dolan, E., Moré, J. Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) https://doi.org/10.1007/s101070100263.

Miscellaneous

Versionning is compliant with Semantic versionning 2.0.0.

hlefebvr/idol