MIP++ (aka MIPpp) is a header‑only C++ library that brings a Pythonic modeling interface to mixed‑integer linear programming. It lets you load multiple solver backends (Gurobi, Cbc, Highs, etc...) at runtime, and uses template metaprogramming to preserve Python‑like syntactic sugar while emitting near‑optimal code at compile time.
Work in progress.
- Header-only: Dynamically loading the C API of solvers allows MIP++ to stay header-only and easy to integrate to C++ projects.
- Modern C++20: Utilizes ranges, lambdas, and template metaprogramming for an elegant and efficient API allowing a Pythonic syntax.
- Solver Agnostic: Supports a variety of solvers (Gurobi, CPLEX, Clp, Cbc, Highs, SoPlex, SCIP, MOSEK, COPT, GLPK and more upcoming) with a unified API.
- High Performance: Optimized for speed with zero cost abstractions and no unnecessary data copying.
git clone
cd mippp
conan create . -u -b=missing -pr=<your_conan_profile>
Then add mippp/<version> as a requirement in your conanfile.txt or conanfile.py.
Simply add mippp/1.0.0 to your conanfile.txt or conanfile.py.
cd <your_project> && mkdir dependencies
git submodule add https://github.com/fhamonic/mippp dependencies/mipppThen in your CMakeLists.txt:
add_subdirectory(dependencies/mippp)
...
target_link_libraries(<some_target> INTERFACE mippp)And ensure that your CMake can find the dylib libraries with find_package calls.
#include "mippp/mip_model.hpp"
using namespace fhamonic::mippp;
using namespace fhamonic::mippp::operators;
...
gurobi_api api("gurobi120"); // loads libgurobi120.so C API
gurobi_lp model(api);
auto x1 = model.add_variable();
auto x2 = model.add_variable({.upper_bound=3});
model.set_maximization();
model.set_objective(4 * x1 + 5 * x2);
model.add_constraint(x1 <= 4);
model.add_constraint(2*x1 + x2 <= 9);
model.solve();
auto sol = model.get_solution();
std::cout << std::format("x1: {}, x2: {}", sol[x1], sol[x2]) << std::endl;Using the MELON library, we can express the Maximum Flow problem as
#include "melon/static_digraph.hpp"
...
melon::static_graph graph = ...;
melon::arc_map_t<decltype(graph), double> capacity_map = ...;
melon::vertex_t<decltype(graph)> s = ...;
melon::vertex_t<decltype(graph)> t = ...;
...
gurobi_api api();
gurobi_lp model(api);
auto F = model.add_variable();
auto X_vars = model.add_variables(graph.num_arcs());
model.set_maximization();
model.set_objective(F);
auto flow_conservation_constrs = model.add_constraints(
graph.vertices(),
[&](auto && u) {
return OPT((u == s), xsum(graph.out_arcs(s), X_vars) ==
xsum(graph.in_arcs(s), X_vars) + F);
},
[&](auto && u) {
return OPT((u == t), xsum(graph.out_arcs(t), X_vars) ==
xsum(graph.in_arcs(t), X_vars) - F);
},
[&](auto && u) {
return xsum(graph.out_arcs(u), X_vars) ==
xsum(graph.in_arcs(u), X_vars);
});
for(auto && a : graph.arcs()) {
model.set_variable_upper_bound(X_vars(a), capacity_map[a]);
}melon::static_graph graph = ...;
std::vector<std::vector<int>> distances = ...
...
gurobi_api api();
gurobi_lp model(api);
auto X_vars = model.add_binary_variables(graph.num_arcs());
model.set_minimization();
model.set_objective(xsum(graph.arcs(), [&](auto && a) {
return distances[graph.arc_source(a)][graph.arc_target(a)] * X_vars(a);
}));
model.add_constraints(graph.vertices(), [&](auto && u) {
return xsum(graph.in_arcs(u), X_vars) == 1;
});
model.add_constraints(graph.vertices(), [&](auto && u) {
return xsum(graph.out_arcs(u), X_vars) == 1;
});
model.set_candidate_solution_callback([&](auto & handle) {
auto solution = handle.get_solution();
auto solution_graph = melon::views::subgraph(
graph, {}, [&](auto a) { return solution[X_vars(a)] > 0.5; });
for(auto && component :
melon::strongly_connected_components(solution_graph)) {
const std::size_t tour_size = component.size();
// if the tour is Hamiltonian no need to add constraints
if(tour_size == graph.num_vertices()) return;
auto component_vertex_filter =
melon::create_vertex_map<bool>(graph, false);
for(const auto & v : component) component_vertex_filter[v] = true;
auto tour_induced_subgraph =
melon::views::subgraph(graph, component_vertex_filter, {});
handle.add_lazy_constraint(
xsum(melon::arcs(tour_induced_subgraph), X_vars) <=
static_cast<int>(tour_size) - 1);
}
});
model.solve();
auto solution = model.get_solution();
auto solution_graph = melon::views::subgraph(
graph, {}, [&](auto a) { return solution[X_vars(a)] > 0.5; });
auto tour = std::ranges::to<std::vector<melon::vertex_t<decltype(graph)>>>(
melon::breadth_first_search(solution_graph, 0u));auto indices = std::views::iota(0, 9);
auto values = std::views::iota(1, 10);
auto 3x3_coords = std::views::cartesian_product(std::views::iota(0, 3),
std::views::iota(0, 3));
gurobi_api api;
gurobi_milp model(api);
auto X_vars =
model.add_binary_variables(9 * 9 * 9, [](int i, int j, int value) {
return (81 * i) + (9 * j) + (value - 1);
});
model.add_constraints( // single value per cell
std::views::cartesian_product(indices, indices), [&](auto && p) {
auto && [i, j] = p;
return xsum(values, [&](auto && v) { return X_vars(i, j, v); }) == 1;
});
model.add_constraints( // unique values within rows
std::views::cartesian_product(values, indices), [&](auto && p) {
auto && [v, i] = p;
return xsum(indices, [&](auto && j) { return X_vars(i, j, v); }) == 1;
});
model.add_constraints( // unique values within cols
std::views::cartesian_product(values, indices), [&](auto && p) {
auto && [v, j] = p;
return xsum(indices, [&](auto && i) { return X_vars(i, j, v); }) == 1;
});
model.add_constraints( // unique values within 3x3 blocks
std::views::cartesian_product(values, 3x3_coords), [&](auto && p) {
auto && [v, b] = p;
return xsum(3x3_coords, [&](auto && p2) {
return X_vars(3 * std::get<0>(b) + std::get<0>(p2),
3 * std::get<1>(b) + std::get<1>(p2), v);
}) == 1;
});
for(auto [i, j, value] : grid_hints) {
model.set_variable_lower_bound(X_vars(i, j, value), 1);
}
model.solve();
auto solution = model.get_solution();
for(auto i : indices) {
for(auto j : indices) {
for(auto v : values) {
if(solution[X_vars(i, j, v)]) std::cout << ' ' << v;
}
}
std::cout << std::endl;
}
- Improve callback support (COPT, HiGHS, Cbc, SCIP, Xpress)
- Add example for Benders decomposition (with and without lazyconstraints)
- Add QP interfaces
- Add model persistance (write/read from file)
- Add special constraints (sos and indicator constraints)