Random sampling and machine learning to understand good decompositions

S. Basso (), A. Ceselli () and A. Tettamanzi ()
Additional contact information
S. Basso: Università degli Studi di Milano
A. Ceselli: Università degli Studi di Milano
A. Tettamanzi: Université Côte d’Azur - INRIA

Annals of Operations Research, 2020, vol. 284, issue 2, No 3, 526 pages

Abstract: Abstract Motivated by its implications in the development of general purpose solvers for decomposable Mixed Integer Programs (MIPs), we address a fundamental research question, that is how to exploit data-driven techniques to obtain automatic decomposition methods. We preliminary investigate the link between static properties of MIP input instances and good decomposition patterns. We devise a random sampling algorithm, considering a set of generic MIP base instances, and generate a large, balanced and well diversified set of decomposition patterns, that we analyze with machine learning tools. We also propose and test a minimal proof of concept framework performing data-driven automatic decomposition. The use of supervised techniques highlights interesting structures of random decompositions, as well as proving (under certain conditions) that data-driven methods are fruitful in our context, triggering at the same time perspectives for future research.

Keywords: Dantzig–Wolfe decomposition; Machine learning; Random sampling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-3067-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-3067-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-3067-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().