Optimization Online


The Strength of Dantzig-Wolfe Reformulations for the Stable Set and Related Problems

Jonas T. Witt (jonas.witt***at***rwth-aachen.de)
Marco E. Lübbecke (marco.luebbecke***at***rwth-aachen.de)

Abstract: Dantzig-Wolfe reformulation of an integer program convexifies a subset of the constraints, which yields an extended formulation with a potentially stronger linear programming (LP) relaxation. We would like to better understand the strength of such reformulations in general. As a first step we investigate the classical edge formulation for the stable set problem. We characterize weakest possible Dantzig-Wolfe reformulations (with LP relaxations not stronger than the edge formulation) and strongest possible reformulations (yielding the integer hull). We (partially) extend our findings to related problems such as the matching problem and the set packing problem. These are the first non-trivial general results about the strength of relaxations obtained from decomposition methods, after Geoffrion's seminal 1974 paper about Lagrangian relaxation.

Keywords: Dantzig-Wolfe reformulation; polyhedral combinatorics; strength of relaxations; stable set

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: RWTH Aachen University, Operations Research, repORt 2015-029

Download: [PDF]

Entry Submitted: 11/20/2015
Entry Accepted: 11/21/2015
Entry Last Modified: 07/06/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society