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.
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.
ZAIK Number: | UNSPECIFIED |
---|---|
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 |