Abstract. In this paper, we consider problem (P ) of minimizing a quadratic function q(x)=xtQx+ctx ofbinary 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 diagonalentries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x2i=x i , wecan 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 devisetwo different preprocessing methods. The first one is straightforward and consists in computing the smallesteigenvalue 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 ourtwo solution methods to several other exact solution methods. Furthermore, we report computational resultsfor the max-cut problem.Key words. Integer programming – Quadratic 0-1 optimization – Convex quadratic relaxation – Semidefinitepositive relaxation – Experiments – Max-cut1. IntroductionConsider the quadratic functionq(x)=xtQx+ctxand 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 supposethat Q is symmetric and also that the diagonal terms of Q are equal to 0. If this is notthe case, Q can be converted to the symmetric form (Q+Qt)/2 and the linear termsq ii x i can be substituted for the diagonal terms q ii x2ibecause x2i=x i for x i? {0, 1}.Problem (P ) is NP-hard and has numerous applications. Consult, for example, (Hansenet al. 2000) and (Boros and Hammer 2001). Furthermore, a recent application of (P ) inthe medical field is reported in (Iasemidis et al. 2001).