# [BEL12] Extending the QCR method to the case of general mixed integer programs

**Revue Internationale avec comité de lecture : **
*Journal Mathematical Programming*,

vol. 131(1),

pp. 381-401,
2012, (

doi:

10.1007/s10107-010-0381-7 )

**Mots clés: ** General integer programming, Mixed-integer programming, Quadratic programming, Convex reformulation, Semi-definite programming, Experiments

**Résumé: **
Abstract. In this paper, we consider problem (P ) of minimizing a quadratic function q(x)
=
x
t
Qx
+
c
t
x of
binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers.
But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal
entries of Q by a vector u until (Q
+
diag(u)) is positive semidefinite. Then, using the fact that x
2
i
=
x i , we
can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence,
computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise
two different preprocessing methods. The first one is straightforward and consists in computing the smallest
eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P ) is solved.
We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our
two solution methods to several other exact solution methods. Furthermore, we report computational results
for the max-cut problem.
Key words. Integer programming Quadratic 0-1 optimization Convex quadratic relaxation Semidefinite
positive relaxation Experiments Max-cut
1. Introduction
Consider the quadratic function
q(x)
=
x
t
Qx
+
c
t
x
and the 0-1 quadratic problem
(P ) : min q(x) : x
∈ {
0,
1}
n
(1)
where Q is an n
×
n real matrix, and c
∈
R n
. Without loss of generality, we can suppose
that Q is symmetric and also that the diagonal terms of Q are equal to 0. If this is not
the case, Q can be converted to the symmetric form (Q
+
Q
t
)/2 and the linear terms
q ii x i can be substituted for the diagonal terms q ii x
2
i
because x
2
i
=
x i for x i
∈ {
0, 1}.
Problem (P ) is NP-hard and has numerous applications. Consult, for example, (Hansen
et al. 2000) and (Boros and Hammer 2001). Furthermore, a recent application of (P ) in
the medical field is reported in (Iasemidis et al. 2001).