Jünger, Michael and Mallach, Sven (2019) Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization.
Published In: 27th Annual European Symposium on Algorithms (ESA 2019), Lipics. Dagstuhl Publishing 6 September 2019, 63:1-63:13.

Abstract

Solving the NP-hard Maximum Cut or Binary Quadratic Optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.

Actions:

Full text not available from this repository.

Editorial actions:	View Item (Login required)