Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

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.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Sven Mallach
Date Deposited: 29 Aug 2019 08:45
Last Modified: 29 Aug 2019 08:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/943