SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more

Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations

In this paper we present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting, that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of … Read more