Groupe d’études et de recherche en analyse des décisions

New Approaches for Optimization over SemiMetric Polytopes

Antonio Frangioni

The semimetric polytope \(M(G)\) associated with a complete undirected graph \(G\) is an important structure in combinatorial optimization, and is related to several relevant optimization problems such as the max-cut problem. The facet-defining inequalities for \(M(G)\), the so-called triangle inequalities, yield an integer linear programming formulation for max-cut and provide its standard LP relaxation. Unfortunately, the linear program defined by the triangle inequalities, which has a number of variables and constraints that is quadratic and cubic on the number of nodes of the graph, respectively, is usually very degenerate and is very hard to solve efficiently for large graphs, even when state-of-the-art linear programming software and constraints generation techniques are used. The rooted semimetric polytope \(RM(G)\) associated with \(G\) is a relaxation of \(M(G)\) defined by those triangle inequalities whose support subgraph contains a selected node of G. RM(G) yields another integer linear programming formulation of max-cut as well as another, although weaker, linear programming relaxation. Based on a new algorithm that is capable of efficiently optimizing a linear function over \(RM(G)\), we construct some Lagrangean-based approaches for maximizing a linear function over \(M(G)\). We report extensive computational results on several classes of graphs which show under which types of graphs each of the different approaches is competitive. In general, the proposed approaches neatly outperform ordinary linear programming techniques, thus, they appear to be a promising new tool for devising exact algorithms for max-cut.