A Compact Variant of the QCR Method for 0-1 Quadratically Constrained Quadratic Programs

Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for 0-1 quadratic programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible.
In this paper, we focus on the case of 0-1 quadratically constrained quadratic programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented.