Optimization Online


Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation

Martin Bergner(martin.bergner***at***rwth-aachen.de)
Alberto Caprara(alberto.caprara***at***unibo.it)
Fabio Furini(fabio.furini***at***unibo.it)
Marco Lübbecke(marco.luebbecke***at***rwth-aachen.de)
Enrico Malaguti(enrico.malaguti***at***unibo.it)
Emiliano Traversi(emiliano.traversi2***at***unibo.it)

Abstract: Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not part of any state-of-the-art MIP solver: it needs tailoring to the particular problem; the typical bordered block-diagonal matrix structure determines the decomposition; the resulting column generation subproblems need to be solved efficiently; branching and cutting decisions need special attention; etc. We perform an extensive computational study on the 0-1 dynamic knapsack problem (without block-diagonal structure) and on general MIPLIB2003 instances in order to (in-)validate such reservations against the method. We present a tool which, given an LP file, automatically detects an exploitable matrix structure, accordingly performs a Dantzig-Wolfe type reformulation of subsets of the constraints (partial convexification), and performs column generation to obtain an optimal LP relaxation. Our results strongly support that Dantzig-Wolfe decomposition holds more promise as a general-purpose tool than previously acknowledged by the research community.

Keywords: mixed integer program; Dantzig-Wolfe decomposition; experimental study

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


Download: [PDF]

Entry Submitted: 11/16/2010
Entry Accepted: 11/16/2010
Entry Last Modified: 11/16/2010

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 Programming Society