Giovanni Rinaldi

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

  • Luigi Grippo
  • Veronica Piccialli
  • Laura Palagi
  • Mauro Piacentini
  • Giovanni Rinaldi
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    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

  • Franz Rendl
  • Giovanni Rinaldi
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming

    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