Motivated by the perspective use in decomposition-based generic Mixed Integer Programming (MIP) solvers, we consider the problem of scoring Dantzig-Wolfe decomposition patterns. In particular, assuming to receive in input a MIP instance, we tackle the issue of estimating the tightness of the dual bound yielded by a particular decomposition of that MIP instance, and the computing time required to obtain such a dual bound, looking only at static features of the corresponding data matrices. We propose decomposition ranking methods. We also sketch and evaluate an architecture for an automatic data-driven detector of good decompositions.
|Titolo:||Computational evaluation of ranking models in an automatic decomposition framework|
|Parole Chiave:||Dantzig-Wolfe decomposition; general purpose solvers; machine learning; Discrete Mathematics and Combinatorics; Applied Mathematics|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||2018|
|Digital Object Identifier (DOI):||10.1016/j.endm.2018.07.032|
|Appare nelle tipologie:||01 - Articolo su periodico|