Exact Facetial OddCycle Separation for Maximum Cut and Binary Quadratic Optimization
Jünger, Michael and Mallach, Sven (2020) Exact Facetial OddCycle Separation for Maximum Cut and Binary Quadratic Optimization.
Abstract
The exact solution of the NPhard 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 socalled oddcycle inequalities. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomialtime 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 facetdefining oddcycle 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://earchive.informatik.unikoeln.de/id/eprint/950 