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 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, Aq_r, Dq_r ∈ S_n , c,c_r ∈ Rⁿ ,bq ∈ R^mq, eq ∈ R ^pq, A ∈ M_mxn , b ∈ R^m , D ∈ M_pxn , e ∈ R^p , ℓ ∈ Rⁿ, and u ∈ Rⁿ,

---

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
u₁ u₂... u_n
ℓ
ℓ₁ ℓ₂... ℓ_n
Q
nnzQ
i j q_ij
C
nnzc
i c_i
A
nnzA r=0,..,m-1
r i a_ri
b
nnzb
r b_r
D
nnzD r=0,..,p-1
r i d_ri
e
nnze
r e_r
Aq
nnzAq_r + nnzc_r r=0..mq-1
r 0 i+1 c_ri
r i+1 j+1 q_rij
bq
nnzbq br/> r bq_r
Dq
nnzDq_r + nnzc_r r=0,..,pq-1
r 0 i+1 c_ri
r i+1 j+1 q_rij
eq
nnzeq
r eq_r
where nnzM_r is the sum of the number of non zero elements of matrices/vectors M_r.

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