2026-07-23T19:56:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11184 2024-03-06T10:47:39Z ddc:004 open_access

Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization Jünger, Michael Mallach, Sven Maximum cut Binary quadratic optimization Integer linear programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Jünger and Sven Mallach 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.63 urn:nbn:de:0030-drops-111840 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.63 eng https://creativecommons.org/licenses/by/3.0/legalcode