On the bridge between combinatorial optimization and nonlinear optimization: new semidefinite bounds for 0-1 quadratic problems leading to Newton methods

SoumisNational audienceThis paper presents new semidefinite programming bounds for 0-1 quadratic problems with linear or quadratic constraints. These bounds are obtained by Lagrangian dualityand convex optimization; and they have interesting numerical features: the tightness is improved by Newton-like method, and the final accuracy level is controlled by real parameter acting like a cursor. This gives ways to trade computing time for a (small) deterioration of the quality of the usual semidefinite bounds, in view of enhancing this efficiency in exact resolution schemes. The numerical properties are illustrated on standard test-problems(unconstrained 0-1 quadratic problems, heaviest k-subgraphs problems, and graph bisection problems). Extensive comparisons with usual bounds (obtained by linear, quadratic or semidefinite programming) are provided on those problems