Automatic Dantzig-Wolfe reformulation of mixed integer programs

被引:38
作者
Bergner, Martin [1 ]
Caprara, Alberto [4 ]
Ceselli, Alberto [2 ]
Furini, Fabio [3 ]
Luebbecke, Marco E. [1 ]
Malaguti, Enrico [4 ]
Traversi, Emiliano [5 ]
机构
[1] Rhein Westfal TH Aachen, D-52072 Aachen, Germany
[2] Univ Milan, Dipartimento Informat, I-26013 Crema, Italy
[3] Univ Paris 09, LAMSADE, F-75775 Paris, France
[4] Univ Bologna, DEI, I-40136 Bologna, Italy
[5] Univ Paris 13, LIPN, Equipe AOC, F-93430 Villetaneuse, France
关键词
Dantzig-Wolfe decomposition; Column generation; Block-diagonal matrix; Matrix re-ordering; Automatic reformulation; Hypergraph partitioning; DECOMPOSITION; MATRICES; LIBRARY;
D O I
10.1007/s10107-014-0761-5
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate the quality of a decomposition: after building a set of potentially good candidates, we exploit such a score to detect which decomposition might be useful for Dantzig-Wolfe reformulation of a MIP. We experiment with general instances from MIPLIB2003 and MIPLIB2010 for which a decomposition method would not be the first choice, and demonstrate that strong dual bounds can be obtained from the automatically reformulated model using column generation. Our findings support the idea that Dantzig-Wolfe reformulation may hold more promise as a general-purpose tool than previously acknowledged by the research community.
引用
收藏
页码:391 / 424
页数:34
相关论文
共 29 条
[1]   MIPLIB 2003 [J].
Achterberg, Tobias ;
Koch, Thorsten ;
Martin, Alexander .
OPERATIONS RESEARCH LETTERS, 2006, 34 (04) :361-372
[2]  
[Anonymous], 50 YEARS INTEGER PRO
[3]  
[Anonymous], 1974, Approaches to integer programming
[4]   Permuting sparse rectangular matrices into block-diagonal form [J].
Aykanat, C ;
Pinar, A ;
Çatalyürek, ÜV .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2004, 25 (06) :1860-1879
[5]  
Bergner M, 2011, LECT NOTES COMPUT SC, V6655, P39, DOI 10.1007/978-3-642-20807-2_4
[6]   Decomposing matrices into blocks [J].
Borndörfer, R ;
Ferreira, CE ;
Martin, A .
SIAM JOURNAL ON OPTIMIZATION, 1998, 9 (01) :236-269
[7]   Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem [J].
Caprara, Alberto ;
Furini, Fabio ;
Malaguti, Enrico .
INFORMS JOURNAL ON COMPUTING, 2013, 25 (03) :560-571
[8]   ROBUST LOCALLY WEIGHTED REGRESSION AND SMOOTHING SCATTERPLOTS [J].
CLEVELAND, WS .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1979, 74 (368) :829-836
[9]   A structure-conveying modelling language for mathematical and stochastic programming [J].
Colombo, Marco ;
Grothey, Andreas ;
Hogg, Jonathan ;
Woodsend, Kristian ;
Gondzio, Jacek .
MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (04) :223-247
[10]  
de Aragao M.P., 2003, MATH PROGRAM RIO C H, P56