文章基本信息

标题：Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
本地全文：下载
作者：Michael J{"u}nger ; Sven Mallach
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：144
页码：1-13
DOI：10.4230/LIPIcs.ESA.2019.63
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Maximum cut; Binary quadratic optimization; Integer linear programming