Lifting and Separation Procedures for the Cut Polytope

Bonato, Thorsten and Jünger, Michael and Reinelt, Gerhard and Rinaldi, Giovanni (2013) Lifting and Separation Procedures for the Cut Polytope.
Published in: Mathematical Programming A. ISSN 0025-5610

Abstract

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, little research has been conducted for the cut polytope on arbitrary graphs. In this study we describe new separation and lifting procedures for the cut polytope on such 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.


Actions:
Download: [img] PDF - Preprinted Version
Download (342Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 06 Feb 2012 08:19
Last Modified: 04 Sep 2013 08:01
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/674