Name
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 implemented in any state-of-the-art MIP solver: it needs tailoring to the particular problem; the decomposition must be determined from the typical bordered block-diagonal matrix structure; the resulting column generation subproblems must be solved efficiently; etc. We provide a computational proof-of-concept that the process can be automated in principle, and that strong dual bounds can be obtained on general MIPs for which a solution by a decomposition has not been the first choice. We perform an extensive computational study on the 0-1 dynamic knapsack problem (without block-diagonal structure) and on general MIPLIB2003 instances. Our results support that Dantzig-Wolfe reformulation may hold more promise as a generalpurpose tool than previously acknowledged by the research community. |
Year | Venue | Keywords |
|---|---|---|
2011 | IPCO | dynamic knapsack problem,partial convexification,block-diagonal matrix structure,strong dual bound,computational proof-of-concept,general mips,block-diagonal structure,extensive computational study,particular problem,dantzig-wolfe reformulation,dantzig-wolfe decomposition,column generation,knapsack problem,proof of concept |
Field | DocType | Volume |
Integer,Mathematical optimization,Column generation,Matrix (mathematics),Computer science,Algorithm,Solver,Knapsack problem | Conference | 6655 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.47 |
References | Authors | |
10 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Bergner | 1 | 19 | 2.26 |
| Alberto Caprara | 2 | 1729 | 160.76 |
| Fabio Furini | 3 | 104 | 16.85 |
| Marco E. Lübbecke | 4 | 490 | 35.19 |
| Enrico Malaguti | 5 | 312 | 21.69 |
| Emiliano Traversi | 6 | 33 | 8.60 |