Optimization Online


A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs

Adam Letchford (A.N.Letchford***at***lancaster.ac.uk)
Laura Galli (l.galli***at***unibo.it)

Abstract: Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 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 quadratically constrained quadratic 0-1 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.

Keywords: combinatorial optimization; semidefinite programming; quadratically constrained quadratic programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Eventually published as: L. Galli & A.N. Letchford (2014) A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs. Optim. Lett., 8(4), 1213-1224.


Entry Submitted: 02/10/2011
Entry Accepted: 02/10/2011
Entry Last Modified: 05/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society