Optimization Online


Dantzig-Wolfe Reformulations for the Stable Set Problem

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 than the original formulation. This paper is part of an endeavor to understand the strength of such a reformulation in general. We investigate the strength of Dantzig-Wolfe reformulations of the classical edge formulation for the maximum weighted stable set problem. Since every constraint in this model corresponds to an edge of the underlying graph, a Dantzig-Wolfe reformulation consists of choosing a subgraph and convexifying all constraints corresponding to edges of this subgraph. We characterize Dantzig-Wolfe reformulations not yielding a stronger LP relaxation (than the edge formulation) as reformulations where this subgraph is bipartite. Furthermore, we analyze the structure of facets of the stable set polytope and present a characterization of Dantzig-Wolfe reformulations with the strongest possible LP relaxation as reformulations where the chosen subgraph contains all odd holes (and 3-cliques). To the best of our knowledge, 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: 11/20/2015

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