Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
Jünger, Michael and Mallach, Sven (2020) Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization.
Abstract
The exact solution of the NP-hard Maximum Cut Problem is important in many applications across, e.g., Physics, Chemistry, Neuroscience, and Circuit Layout – which is also due to its equivalence to the unconstrained Binary Quadratic Optimization Problem. Leading solution methods are based on linear or semidefinite programming, and require the separation of the so-called odd-cycle inequalities. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the obtained inequalities correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison to an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities.
Item Type: | Article |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | |
Subjects: |
|
Divisions: | UNSPECIFIED |
Additional Information: | (accepted, within publication process) |
Related URLs: |
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Sven Mallach |
Date Deposited: | 21 Oct 2020 11:52 |
Last Modified: | 04 Mar 2021 14:02 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/950 |