A cutting plane algorithm for the max-cut problem
Caterina De Simone, Giovanni Rinaldi · Optimization methods & software · 1994
In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem over the cut cone and we give a separation algorithm for a class of inequalities valid over the cut cone: the hypermetric inequalities. Computational results are given.