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.
This library is intended to be added as git and cmake submodules with
[submodule "dependencies/mippp"]
path = dependencies/mippp
url = https://github.com/fhamonic/mipppand
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.
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.
#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);
}