@inproceedings{29b796ccd6664e5d9a0d2909693e0bf1,
title = "Learning when to use a decomposition",
abstract = "Applying a Dantzig-Wolfe decomposition to a mixed-integer program (MIP) aims at exploiting an embedded model structure and can lead to significantly stronger reformulations of the MIP. Recently, automating the process and embedding it in standard MIP solvers have been proposed, with the detection of a decomposable model structure as key element. If the detected structure reflects the (usually unknown) actual structure of the MIP well, the solver may be much faster on the reformulated model than on the original. Otherwise, the solver may completely fail. We propose a supervised learning approach to decide whether or not a reformulation should be applied, and which decomposition to choose when several are possible. Preliminary experiments with a MIP solver equipped with this knowledge show a significant performance improvement on structured instances, with little deterioration on others.",
keywords = "Automatic Dantzig-Wolfe decomposition, Branch-and-price, Column generation, Mixed-integer programming, Supervised learning",
author = "Markus Kruber and L{\"u}bbecke, \{Marco E.\} and Axel Parmentier",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017 ; Conference date: 05-06-2017 Through 08-06-2017",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-59776-8\_16",
language = "English",
isbn = "9783319597751",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "202--210",
editor = "Domenico Salvagnin and Michele Lombardi",
booktitle = "Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Proceedings",
}