SDP Based Solution Methods for Binary Quadratic Problems

Binary quadratic programs (BQP) with equality constraints have a convex quadratic function, linear equality constrains and binary variables. Many problems, like Max-Cut, kcluster, ... can be modeled as BQP. A wide range of solution techniques were proposed and studied in the past in order to solve the problem either to optimality or with heuristics. We present some approaches such as exact penalization methods,

branch and bound and a bundle algorithm in combination with semidefinite relaxations. Then we see the possible combinationsbetweentheminordertoobtainpracticalresults. In this talk we explain some of the choices throughout the algorithms and we exploit their practical performance, relating it with computational time for some testbed examples. Furthermorewecompareourresultsforthebinaryquadraticproblem with other approaches, first for unconstrained problems and then to instances with equality constraints.