General mixed-integer quadratic problem instances

Problem Description

Files format

The instances files

A few references where these instances are used

Problem description

This library contains instances of linearly constrained Mixed Integer Quadratic Programs (MIQP) that can be formulated as follows:

Min f(x) = xt Q x + ct x
(MIQP) s.t.
Ax = b m linear equalities
Dx ≤ e p linear inequalities
0 ≤ ℓ ≤ x ≤ u n positive and upper bounded variables
xi ∈ N i=1,..,nb_int integer variables
xi ∈ R i=nb_int,...,n real variables

Where Q ∈ Sn, c ∈ Rn, A ∈ Mmxn, b ∈ Rm, D ∈ Mpxn, e ∈ Rp, ℓ ∈ Rn and u ∈ Rn. In these instances, the submatrix of pure real quadratic terms of matrix Q defined by (q(ij) ∈ {nb_int..n}x{nb_int..n} is positive semidefinite.

Files format  

Each .dat file contains one instance, in the format of solver SMIQP:
n nb_int m p 0 0
u1 u2... un

12... ℓn
i j qij
i ci
r i ari
r br
s i dsi
s es
where nnzM is the number of non zero elements of matrix/vector M.

An example is available here  

The optimal solution values are reported here :

  • The EIQP-IIQP instance files  


    [1] 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

    [2] 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)

    [3] 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}

    [4] A. Billionnet, S. Elloumi and A. Lambert - Solving a general mixed-integer quadratic problem through convex reformulation : a computational study , European Workshop on Mixed Integer Nonlinear Programming, April 2010, pp.197-204, Marseille, France

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

    [6] 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 SMIQP

    Back to Equipe OC

    Back to CEDRIC