MIQP solver based on OSQP
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
examples
extra Minor cleanup Mar 20, 2017
max_iter_examples Minor changes printing. Added new problem Feb 27, 2017
miosqp Fixed typo with non ASCII character Nov 1, 2017
results Added setup.py file. Added usage description README Oct 30, 2017
.gitignore Added setup.py file. Added usage description README Oct 30, 2017
LICENSE
README.md Added pdf link Oct 30, 2018
run_examples.py Added setup.py file. Added usage description README Oct 30, 2017
setup.py Added setup.py file. Added usage description README Oct 30, 2017

README.md

Mixed-Integer Quadratic Program Solver Based on OSQP

miOSQP solves an mixed-integer quadratic programs (MIQPs) of the form

minimize        0.5 x' P x + q' x

subject to      l <= A x <= u
                x[i] in Z for i in i_idx
                i_l[i] <= x[i] <= i_u[i] for i in i_idx

where i_idx is a vector of indices of which variables are integer and i_l, i_u are the lower and upper bounds on the integer variables respectively.

Installation

To install the package simply run

python setup.py install

it depends on OSQP, numpy and scipy.

Usage

To solve a MIQP we need to run

import miosqp
m = miosqp.MIOSQP()
m.setup(P, q, A, l, u, i_idx, i_l, i_u)
results = m.solve()

where P is a symmetric positive semidefinite matrix and A a matrix. P and A are both in the scipy sparse CSC format.

The returned object results contains

  • x: the solution
  • upper_glob: the cost function upper bound
  • run_time: the solution time
  • status: the status
  • osqp_solve_time: the OSQP solve time as a percentage of the total solution time
  • osqp_iter_avg: the OSQP average number of iterations for each QP sub-problem solution

Update problem vectors

Problem vectors can be updated without running the setup again. It can be done with

m.update_vectors(q=q_new, l=l_new, u=u_new)

Set initial solution guess

The initial guess can speedup the branch-and-bound algorithm significantly. To set an initial feasible solution x0 we can run

m.set_x0(x0)

Citing

If you are using this package for your work, please cite the following paper:

@inproceedings{stellato2018,
  author = {Stellato, B. and Naik, V. V. and Bemporad, A. and Goulart, P. and Boyd, S.},
  title = {Embedded Mixed-Integer Quadratic Optimization Using the {OSQP} Solver},
  booktitle = {European Control Conference ({ECC})},
  year = {2018},
  code = {https://github.com/oxfordcontrol/miosqp},
  month = jul,
  groups = {power electronics, integer programs}
}

Run examples

In order to run the examples from to compare with GUROBI, after installing the python insterface, you need to install mathprogbasepy. Examples can be found in the examples folder.

  • Random MIQPs
  • Power system example

Note that you need pandas package for storing the results dataframe and tqdm package for the progress bar.