Random sampling and machine learning to understand good decompositions - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2020

Random sampling and machine learning to understand good decompositions

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (902.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02319521 , version 1 (18-10-2019)

Identifiants

Citer

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⟩
287 Consultations
188 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More