Data Driven Algorithms and Distributed Computing for Automatic MIP Decompositions

Abstract

Motivated by its implications in the development of general purpose solvers, we address a fundamental research question, that is how to exploit Dantzig-Wolfe decomposition methods for generic Mixed Integer Programs (MIP). In the first part of the thesis, we research how to obtain such decompositions in an automatic fashion. We investigate, with machine learning tools, the link between static properties and good decomposition patterns, highlighting interesting structures. Then, we propose a fully data driven detector, capable of producing good decompositions, and a data driven local search algorithm to reformulate and enhance them. We develop a computational effective framework and test it on unseen MIPs, obtaining better results than state-of-the-art detectors. In the second part of the thesis, we design a concurrent computing framework, which is able to exploit massive parallelism when decompositions allow so. We develop asynchronous and distributed column generation algorithms. Our approach turns out to be, on average, one order of magnitude faster than state-of-the-art solvers.