An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., <CitationRef CitationID="CR3">2010</CitationRef>) a general solution method based on quadratic convex reformulation, that we called <Emphasis FontCategory="NonProportional">MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by <Emphasis FontCategory="NonProportional">MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than <Emphasis FontCategory="NonProportional">MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation <Emphasis FontCategory="NonProportional">(CQCR). We evaluate <Emphasis FontCategory="NonProportional">CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that <Emphasis FontCategory="NonProportional">CQCR is much faster than <Emphasis FontCategory="NonProportional">MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User’s manual, <CitationRef CitationID="CR25">2010</CitationRef>) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare <Emphasis FontCategory="NonProportional">MIQCR and <Emphasis FontCategory="NonProportional">CQCR on instances of the Constrained Task Assignment Problem. These experiments show that <Emphasis FontCategory="NonProportional">CQCR can solve instances that <Emphasis FontCategory="NonProportional">MIQCR and other existing methods fail to solve. Copyright Springer Science+Business Media, LLC 2013