
Automatic Dantzig–Wolfe reformulation of mixed integer programs
Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano (2015), Automatic Dantzig–Wolfe reformulation of mixed integer programs, Mathematical Programming, 149, 1-2, p. 391-424. 10.1007/s10107-014-0761-5
View/ Open
Type
Article accepté pour publication ou publiéDate
2015Journal name
Mathematical ProgrammingVolume
149Number
1-2Publisher
Springer
Pages
391-424
Publication identifier
Metadata
Show full item recordAuthor(s)
Bergner, MartinCaprara, Alberto
Ceselli, Alberto
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lübbecke, Marco E.
Malaguti, Enrico
Traversi, Emiliano
Laboratoire d'Informatique de Paris-Nord [LIPN]
Abstract (EN)
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.Subjects / Keywords
Dantzig–Wolfe decomposition; Column generation; Block-diagonal matrix; Matrix re-ordering; Automatic reformulation; Hypergraph partitioningRelated items
Showing items related by title and author.
-
Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
-
Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
-
Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
-
Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié