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. Keywords: Dantzig-Wolfe Decomposition, Machine Learning, Random Sampling.

Random Sampling and Machine Learning to Understand Good Decompositions / S. Basso, A. Ceselli, A. Tettamanzi. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 1572-9338. - 284:2(2020 Jan), pp. 501-526.

Random Sampling and Machine Learning to Understand Good Decompositions

S. Basso;A. Ceselli
;
2020

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. Keywords: Dantzig-Wolfe Decomposition, Machine Learning, Random Sampling.
Dantzig-Wolfe Decomposition; Machine Learning; Random Sampling
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
   Towards Research on decomposition Methods for Next Generation Analytics
   FONDAZIONE CARIPLO
   2015-0717
gen-2020
2018
Article (author)
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 914.23 kB
Formato Adobe PDF
914.23 kB Adobe PDF Visualizza/Apri
Basso2020_Article_RandomSamplingAndMachineLearni.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 2.03 MB
Formato Adobe PDF
2.03 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/487931
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact