DIMACS TR: 93-18

Convex Relaxations of 0-1 Quadratic Programming

Authors: Svatopluk Poljak and Henry Wolkowicz


We consider three parametric relaxations of the 0-1 quadratic programming problem. These relaxations are to: quadratic maximization over simple box constraints, quadratic maximization over the sphere, and the maximum eigenvalue of a bordered matrix. When minimized over the parameter, each of the relaxations provides an upper bound on the original discrete problem. Moreover, these bounds are efficiently computable. Our main result is that, surprisingly, all three bounds are equal. Henry Wolkowicz; Department of Combinatorics and Optimization; Faculty of Math.; Univ. of Waterloo; Waterloo, Ont., Canada N2L 3G1 (on sabbatical leave at Princeton University, Dept. of Civil Engineering and Operations Research, Princeton, NJ 08544, 609-258-3839) {hwolkowicz@orion.uwaterloo.ca; na.wolkowicz@na-net.ornl.gov}

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-18.ps
DIMACS Home Page