Optimization Online


Random Sampling and Machine Learning to Understand Good Decompositions

Saverio Basso (svr.basso***at***gmail.com)
Alberto Ceselli (alberto.ceselli***at***unimi.it)
Andrea Tettamanzi (andrea.tettamanzi***at***unice.fr)

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

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: University of Milan, Tech. Rep. 2434/487931, March 2017

Download: [PDF]

Entry Submitted: 03/25/2017
Entry Accepted: 03/26/2017
Entry Last Modified: 05/19/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society