Bonato, Thorsten ORCID: 0000-0002-9874-2314, Juenger, Michael, Reinelt, Gerhard and Rinaldi, Giovanni ORCID: 0000-0003-0148-2470 (2014). Lifting and separation procedures for the cut polytope. Math. Program., 146 (1-2). S. 351 - 379. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

Abstract

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Bonato, ThorstenUNSPECIFIEDorcid.org/0000-0002-9874-2314UNSPECIFIED
Juenger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Reinelt, GerhardUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Rinaldi, GiovanniUNSPECIFIEDorcid.org/0000-0003-0148-2470UNSPECIFIED
URN: urn:nbn:de:hbz:38-432920
DOI: 10.1007/s10107-013-0688-2
Journal or Publication Title: Math. Program.
Volume: 146
Number: 1-2
Page Range: S. 351 - 379
Date: 2014
Publisher: SPRINGER HEIDELBERG
Place of Publication: HEIDELBERG
ISSN: 1436-4646
Language: English
Faculty: Unspecified
Divisions: Unspecified
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
BICYCLE WHEEL INEQUALITIES; EXACT GROUND-STATES; ISING SPIN-GLASSES; COMBINATORIAL OPTIMIZATION; TRIANGULAR ELIMINATION; BELL INEQUALITIES; FACETS; ALGORITHMSMultiple languages
Computer Science, Software Engineering; Operations Research & Management Science; Mathematics, AppliedMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/43292

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item