In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x' and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which is a related set studied in [S. Burer and A. N. Letchford, On nonconvex quadratic programming with box constraints, SIAM J. Optim, 2009]. After closing a theoretical gap about QPB, we characterize the strength of different classes of lifted inequalities. We show that although one class, which we call lifted PosDiag inequalities, capture no information on the binary indicators, the other class, called lifted concave inequalities, are quite important. We illustrate this from two aspects. First, it contains all perspective cuts. When add these cuts to a semidefinite relaxation of convex quadratic programs with binary indicators, with mild constraint qualifications, we obtain an SDP that is equivalent to the ``optimal" diagonal splitting approach. Second, the full lifted concave class are all we need to solve convex quadratic programming with binary indicators. Finally we show the separation problem for lifted concave inequalities is polynomially solvable if the number of binary variables involved is fixed. Several interesting questions arise from our results, which we detail in our discussion section.
Citation
Manuscript, Wisconsin Institutes for Discovery, University of Wisconsin-Madison, 08/2012.
Article
View On valid inequalities for quadratic programming with continuous variables and binary indicators