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.
Article
View Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation