Universität zu Köln

Juenger, Michael and Mallach, Sven ORCID: 0000-0001-5335-0678 (2021). Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization. INFORMS J. Comput., 33 (4). S. 1419 - 1431. CATONSVILLE: INFORMS. ISSN 1526-5528

Full text not available from this repository.

Abstract

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, 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 research, 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 inequalities obtained 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 with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Juenger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mallach, Sven UNSPECIFIED orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-571025
DOI:	10.1287/ijoc.2020.1008
Journal or Publication Title:	INFORMS J. Comput.
Volume:	33
Number:	4
Page Range:	S. 1419 - 1431
Date:	2021
Publisher:	INFORMS
Place of Publication:	CATONSVILLE
ISSN:	1526-5528
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language EXACT GROUND-STATES; ALGORITHM; INEQUALITIES; POLYTOPE Multiple languages Computer Science, Interdisciplinary Applications; Operations Research & Management Science Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/57102