TY - GEN A1 - Helmberg, Christoph T1 - A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations N2 - The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably. T3 - ZIB-Report - 01-26 KW - bisection KW - equicut KW - max-cut KW - semidefinite programming KW - spectral bundle method KW - subgradient method KW - quadratic 0-1 programming Y1 - 2001 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/652 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-6527 ER -