Solver of Mixed-Integer Quadratic Programs (SMIQP)


SMIQP

Files format

Download the code

References


Solver of Mixed-Integer Quadratic Programs (SMIQP)

SMIQP is an open-source C code for solving general MIQCQP (Mixed Integer Quadratically Constrained Quadratic Programs) problems of the form:

Min f(x) = xt Q x + ct x
(MIQCPm) s.t.
xt Aqr x + c r t x = bqr r=0, ..., mq-1 : mq quadratic equalities equalities
xt Dqr x + c r t x ≤ eqr r=0, ..., pq-1 : pq quadratic inequalities
Ax = b m linear equalities
Dx ≤ e p linear inequalities
0 ≤ ℓ ≤ x ≤ u n positive and lower and upper bounded variables
xi ∈ N i=0,..,nb_int-1 : nb_int integer variables
xi ∈ R i=nb_int,...,n : n-nb_int real variables

Where Q, Aqr, Dqr ∈ Sn , c,cr ∈ Rn ,bq ∈ Rmq, eq ∈ R pq, A ∈ Mmxn , b ∈ Rm , D ∈ Mpxn , e ∈ Rp , ℓ ∈ Rn, and u ∈ Rn,





SMIQP is a software package for solving quadratic optimisation problems with mixed-integer variables. This project is a C code that uses CSDP , the Conic Bundle Library , and Ipopt subroutines. It can also use Cplex or Scip as sub-solvers. The solver is the implementation of algorithm MIQCR of Billionnet, Elloumi and Lambert [1-8]. It is available under the EPL (Eclipse Public License) open-source license.

Authors of the code and project manager: Amélie Lambert.


Download the code  

The code is available Smiqp-1.0.zip.
For installation (from sources) instruction see INSTALL file. More information on SMIQP installation and usage can be found here , or you can download a short tutorial .



Files format  

The solver SMIQP reads the following format:
n nb_int m p mq pq
u
u1 u2... un

12... ℓn
Q
nnzQ
i j qij
C
nnzc
i ci
A
nnzA r=0,..,m-1
r i ari
b
nnzb
r br
D
nnzD r=0,..,p-1
r i dri
e
nnze
r er
Aq
nnzAqr + nnzcr r=0..mq-1
r 0 i+1 cri
r i+1 j+1 qrij
bq
nnzbq br/> r bqr
Dq
nnzDqr + nnzcr r=0,..,pq-1
r 0 i+1 cri
r i+1 j+1 qrij
eq
nnzeq
r eqr
where nnzMr is the sum of the number of non zero elements of matrices/vectors Mr.

An example is available here  

References

[1] S. Elloumi and A. Lambert. Global solution of non-convex quadratic=ally constrained quadratic programs Optimization Methods and Software 34 (1): 98-114, (2019) DOI: 10.1080/10556788.2017.1350675

[2] A. Billionnet, S. Elloumi, A. Lambert and A. Wiegele. Using a conic bundle method to accelerate both phases of a quadratic convex reformulation Informs Journal on computing. 29 (2), 318-331 (2017) DOI: 10.1287/ijoc.2016.0731

[3] A. Billionnet, S. Elloumi and A. Lambert. Exact quadratic convex reformulations of mixed-integer quadratically constrained problems Mathematical Programming serie A. 158 (1), 235-266 (2016) DOI: 10.1007/s10107-015-0921-2

[4] A. Billionnet, S. Elloumi and A. Lambert. A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation, Journal of Combinatorial Optimization. 28(2), 376-399 (2015) DOI: 10.1007/s10878-012-9560-1

[5] A. Billionnet, S. Elloumi and A. Lambert. An efficient compact quadratic convex reformulation for general integer quadratic programs. Computational Optimization and Applications. (54) 141-162, 2013 (DOI: 10.1007/s10589-012-9474-y)

[6] A. Billionnet, S. Elloumi and A. Lambert. Extending the QCR method to general mixed integer programs. Mathematical Programming (series A). vol. 131( 1), pp. 381-401, 2012. DOI: 10.1007/s10107-010-0381-7}

[7] A. Lambert. Résolution de programmes quadratiques en nombres entiers. Thèse de Doctorat en informatique, CEDRIC, (2009). PhD thesis

[8] A. Billionnet, S. Elloumi and A. Lambert. Linear Reformulations of Integer Quadratic Programs. MCO 2008, Metz, september 8-10, pp. 43-51, 2008. (pdf)


Back to Main page

Back to Library

Back to Equipe OC

Back to CEDRIC