It has recently been shown (Burer, 2006) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs (CPPs), i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are necessarily NP-hard. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods (IPMs). In this paper, we propose a decomposition technique, which approximately solves the DNPs in a practically efficient manner, while simultaneously producing lower bounds on the original NQP. Our method is inspired by, but different from, a related decomposition technique of Burer and Vandenbussche (2006). Compared to IPMs and Burer-Vandenbussche, we illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For a few quadratic assignment instances, best-known lower bounds are obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.
Citation
Technical report, Department of Management Sciences, University of Iowa, December 2008.
Article
View Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs