A cutting plane algorithm for the max-cut problem
De Simone, C.; Rinaldi, G.; De Simone, C.; Istituto di Analisi dei Sistemi ed Inforrnatica del CNR; Rinaldi, G.; Istituto di Analisi dei Sistemi ed Inforrnatica del CNR
Журнал:
Optimization Methods and 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.
589.8Кб