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