"Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming"Anstreicher, KurtLet ${\rm Box}_n$ denote the unit hypercube in $\Re^n$, and let ${\rm QPB}_n$ denote the convex hull of $\{(1, x^T)^T(1, x^T) : x\in {\rm Box}_n\}$. The quadratic programming problem $\min\{x^T Q x + q^T x : x\in{\rm Box}_n\}$ where $Q$ is not positive semidefinite (PSD), is equivalent to a linear optimization problem over ${\rm QPB}_n$ and could be efficiently solved if a tractable characterization of ${\rm QPB}_n$ was available. It is known that ${\rm QPB}_2$ can be represented using a PSD constraint combined with constraints generated using the reformulation-linearization technique (RLT). The triangle (TRI) inequalities are also valid for ${\rm QPB}_3$, but the PSD, RLT and TRI constraints together do not fully characterize ${\rm QPB_3}$. In this paper we describe new valid linear inequalities for ${\rm QPB}_n$, $n\ge 3$ based on strengthening the approximation of ${\rm QPB}_3$ given by the PSD, RLT and TRI constraints. These new inequalities are generated in a systematic way using a known disjunctive characterization for ${\rm QPB}_3$. We also describe a conic strengthening of the linear inequalities that incorporates second-order cone constraints. We show computationally that the new inequalities and their conic strengthenings obtain exact solutions for some nonconvex box-constrained instances that are not solved exactly using the PSD, RLT and TRI constraints. Joint work with Diane Puges, Klagenfurt. |
« back