MIPpp

MIPpp is a attempt to provide a way for efficiently instanciate Mixed Integer Linear Programs in C++ in a Python-MIP fashion. Like Python-MIP, the aim is to support several MILP solvers as backends (currently CBC, SCIP and GUROBI). The use of template metaprogramming allows to retain most of the syntactical sugars available in python while generating near optimal code at compile time.

Work in progress.

How to link

As git and cmake submodules (recommended)

This library is intended to be added as git and cmake submodules with

[submodule "dependencies/mippp"]
    path = dependencies/mippp
    url = https://github.com/fhamonic/mippp

and

add_subdirectory(dependencies/mippp)
...
target_link_libraries(<some_target> INTERFACE mippp)

Until C++23, the Range-v3 library is mandatory for some ranges functionnalities. This project use the Conan C++ package manager is used to automatically resolve this dependency.

As a single-header

The single header is generated in the single-header folder with

make single-header

then manage to #include it where needed with the range-v3 library.

Code examples

#include "mippp/mip_model.hpp"
#include "mippp/operators.hpp"
using namespace fhamonic::mippp;
...
using MIP = mip_model<linked_cbc_traits>;
MIP model;
auto x1 = model.add_variable();
auto x2 = model.add_variable({.upper_bound=3}); // default option is
// {.obj_coef=0, .lower_bound=0, .upper_bound=infinity, type=MIP::var_category::continuous}
model.add_to_objective(4 * x1 + 5 * x2);
model.add_constraint(x1 <= 4);
model.add_constraint(2*x1 + x2 <= 9);

auto solver_model = model.build();
solver_model.optimize();
std::vector<double> solution = solver_model.get_solution();

Using the MELON library, we can express the Maximum Flow problem as

#include "melon/static_digraph.hpp"
using namespace fhamonic::melon;

#include "mippp/mip_model.hpp"
#include "mippp/operators.hpp"
#include "mippp/xsum.hpp"
using namespace fhamonic::mippp;
...
static_graph graph = ...;
arc_map_t<static_graph, double> capacity_map = ...;
vertex_t<static_graph> s = ...;
vertex_t<static_graph> t = ...;

mip_model<linked_cbc_traits> model;
auto F = model.add_variable();
auto X_vars = model.add_variables(graph.nb_arcs(),
    [](arc_t<static_graph> a) -> std::size_t { return a; });

model.add_to_objective(F);
for(auto && u : graph.vertices()) {
    if(u == s || u == t) continue;
    model.add_constraint(xsum(graph.out_arcs(u), X_vars) == xsum(graph.in_arcs(u), X_vars));
}
model.add_constraint(xsum(graph.out_arcs(s), X_vars) == xsum(graph.in_arcs(s), X_vars) + F);
model.add_constraint(xsum(graph.out_arcs(t), X_vars) == xsum(graph.in_arcs(t), X_vars) - F);
for(auto && a : graph.arcs()) {
    model.add_constraint(X_vars(a) <= capacity_map[a]);
}

or the Shortest Path problem as

static_graph graph = ...;
arc_map_t<static_graph, double> length_map = ...;
vertex_t<static_graph> s = ...;
vertex_t<static_graph> t = ...;

using MIP = mip_model<linked_cbc_traits>;
MIP model(MIP::opt_sense::min);
auto X_vars = model.add_variables(graph.nb_arcs(),
    [](arc_t<static_graph> a) -> std::size_t { return a; });

model.add_to_objective(xsum(graph.arcs(), X_vars, length_map));
for(auto && u : graph.vertices()) {
    const double extra_flow = (u == s ? 1 : (u == t ? -1 : 0));
    model.add_constraint(
        xsum(graph.out_arcs(u), X_vars) == xsum(graph.in_arcs(u), X_vars) + extra_flow);
}