Optimization Online


A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

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

Abstract: In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study aims at better understanding of what happens in between these extremes. For a collection of integer programs with few constraints we compute, optimally solve, and evaluate the relaxations of all possible (exponentially many) Dantzig-Wolfe reformulations (with mild extensions to larger models from the MIPLIBs). We observe that only a tiny number of different dual bounds actually occur and that only a few inclusion-wise minimal representatives exist for each. This aligns with considerably different impacts of individual constraints on the strengthening the relaxation, some of which have almost no influence. In contrast, types of constraints that are convexified in textbook reformulations have a larger effect. We relate our experiments to what could be called a hierarchy of Dantzig-Wolfe reformulations.

Keywords: Dantzig-Wolfe reformulation; strength of reformulations; Lagrangean relaxation; partial convexification; column generation; hierarchy of relaxations

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: report 2018-047, RWTH Aachen University, February 2018

Download: [PDF]

Entry Submitted: 02/26/2018
Entry Accepted: 02/26/2018
Entry Last Modified: 07/12/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