Skip to Main content Skip to Navigation
New interface
Journal articles

Random sampling and machine learning to understand good decompositions

Saverio Basso 1 Alberto Ceselli 1 Andrea G. B. Tettamanzi 2 
2 WIMMICS - Web-Instrumented Man-Machine Interactions, Communities and Semantics
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - SPARKS - Scalable and Pervasive softwARe and Knowledge Systems
Abstract : Motivated by its implications in the development of general purpose solvers for decomposable Mixed Integer Programs (MIP), we address a fundamental research question, that is to assess if good decomposition patterns can be consistently found by looking only at static properties of MIP input instances, or not. We adopt a data driven approach, devising a random sampling algorithm, considering a set of generic MIP base instances, and generating a large, balanced and well diversified set of decomposition patterns, that we analyze with machine learning tools. The use of both supervised and unsupervised techniques highlights interesting structures of random decompositions, as well as suggesting (under certain conditions) a positive answer to the initial question, triggering at the same time perspectives for future research.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Andrea G. B. Tettamanzi Connect in order to contact the contributor
Submitted on : Friday, October 18, 2019 - 9:08:24 AM
Last modification on : Tuesday, November 22, 2022 - 5:32:24 PM
Long-term archiving on: : Sunday, January 19, 2020 - 1:22:57 PM


Files produced by the author(s)




Saverio Basso, Alberto Ceselli, Andrea G. B. Tettamanzi. Random sampling and machine learning to understand good decompositions. Annals of Operations Research, 2020, 284 (2), pp.501-526. ⟨10.1007/s10479-018-3067-9⟩. ⟨hal-02319521⟩



Record views


Files downloads