This is a Mixed Integer Quadratic Programming solver for python exploiting sparsity.
Internally it uses CoinOR's general MINLP-solver Bonmin (which uses other CoinOR projects like Cbc and Ipopt) and prepares the necessary internals tuned for instances of Quadratic Programming like structure- and function-definitions including Jacobian / Hessian of the Lagrangian information).
In general, Bonmin tackles MINLP (Mixed Integer NonLinear Programming) problems which is more general than MIQP (Mixed Integer Quadratic Programming) problems, but the performance, when specialized commercial solvers (Gurobi, CPLEX, Mosek; some potentially limited to CMIQP -> convex) are unavailable, is good (only open-source + free solver considered in this Benchmark)!
For convex problems, Bonmin guarantees a global-optimum, while it only guarantees a local-optimum for nonconvex problems.
Prototype
It's working for small constrained examples. But heavy-testing has not been done yet and it's to be expected, that there are bugs.
I'm rediscovering C++ right now and the C++-part in this project is sub-optimal at least!
min c.T x + 0.5 * x.T Q x
subject to: glb <= A x <= gub
lb <= x <= ub
x_i in Z for all i in I and,
x_i in R for all i not in I.
with:
c: n real vector
Q: symmetric n*n real matrix
convex if Q is positive-semidefinite
A: m*n real matrix
glb: m real vector
gub: m real vector
lb: n real vector
ub: n real vector
From this follows, that only linear-constraints are supported (limited by this wrapper; not due to Bonmin)!
This wrapper uses pybind11 to combine C++ and Python.
The setuptools-based install is based on pybind/python_example.
Eigen is used for most (sparse) calculations.
The implementation assumes the usage of sparse-matrices (for Q + A), provided by scipy.sparse (see tests) and numpy-arrays (for vectors) provided by numpy.
See tests folder. E.g. test_0.py
:
import numpy as np
import scipy.sparse as sp
from pyMIQP import MIQP
"""
Example from OPTI:
https://www.inverseproblem.co.nz/OPTI/index.php/Probs/MIQP
Example 1: Small MIQP
"""
Q = sp.csc_matrix(np.array([[1,-1],[-1,2]]))
c = np.array([-2, -6])
A = sp.csc_matrix(np.array([[1,1],[-1,2], [2,1]]))
glb = np.array([-np.inf, -np.inf, -np.inf])
gub = np.array([2,2,3])
xlb = np.array([0,0])
xub = np.array([np.inf, np.inf])
# 0, 1, 2 = cont, bin, int
var_types = np.array([2, 0])
miqp = MIQP(hessian_approximation=False) # redundant: default -> exact-hessian
miqp.set_c(c)
miqp.set_Q(Q)
miqp.set_A(A)
miqp.set_glb(glb)
miqp.set_gub(gub)
miqp.set_xlb(xlb)
miqp.set_xub(xub)
miqp.set_var_types(var_types)
miqp.set_initial_point(np.array([0, 0])) # redundant: default init-vec -> zeros
miqp.solve(algorithm="B-Hyb") # redundant: default algorithm -> B-Hyb
print('sol-status: ', miqp.get_sol_status())
print('sol-obj: ', miqp.get_sol_obj())
print('sol-x: ', miqp.get_sol_x())
print('sol-time (ms): ', miqp.get_sol_time())
Only the combination of Linux (Ubuntu-like) and python3 was tested!
Make sure to respect all those licenses (a lot of software involved).
- Prepare your system to be able to build software (
sudo apt install build-essential
and co.)- The following might suffice (no guarantees):
sudo apt-get install gfortran gcc g++ autotools-dev automake autoconf
- The following might suffice (no guarantees):
- Grab a release (e.g. from github)
- Release because: we need the ThirdParty folder (not shipped with all kinds of source-grabbing approaches)!
- We are approaching a free open-source build here (
Cbc
shipped;Ipopt
shipped; ```Mumps````used as Linear-solver; will be grabbed)- Other configs were not tested!
- cd to
ThirdParty/Blas
./get.Blas
- cd to
ThirdParty/Lapack
./get.Lapack
- cd to
ThirdParty/Mumps
./get.Mumps
- cd to core-dir
./configure --prefix=/usr --enable-cbc-parallel --enable-gnu-packages
- (global-install is used so that bonmin's lib is automatically found)
make -j 4
- (
make test
) sudo make install
- Eigen is a header-only library and it's expected that the folder can be found at:
src/Eigen
src/Eigen/src/Eigen
is available
sudo python3 setup.py install
- C++ style-formatting: very ugly mixed-style code for now
- C++ code quality improvements: partially non-nice C++ Code
- Support more of Bonmin's options
-
Support options to control verbosity(global verbose-switch only for now) - Error-handling
- Tests
- (maybe) consider supporting MIQCQP (quadratic constraints) or MISOCP (second-order cone constraints)
-
Provide Hessian-calculations to not use Ipopt's Hessian-approximation -
Write an interface for cvxpy's newly introduced QP-pipeline
The only alternatives known to the author:
- Pyomo
- Very complete and mature software with sparse documentation
- Not limited to QPs
- As far as the author knows: Bonmin-usage completely based on AMPL Solver Library (file-based?)
- Usage resembles mathematical-modelling languages
- CasADi
- Very complete software
- Not limited to QPs