The strength of Dantzig-Wolfe reformulations for the stable set and related problems

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. (C) 2018 Elsevier B.V. All rights reserved.