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.

DATA DRIVEN ALGORITHMS AND DISTRIBUTED COMPUTING FOR AUTOMATIC MIP DECOMPOSITIONS

BASSO, SAVERIO
2021

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.
22-mar-2021
Inglese
Mathematical Programming; Machine Learning; Distributed Computing; Dantzig-Wolfe decomposition; Column Generation
CESELLI, ALBERTO
BOLDI, PAOLO
Università degli Studi di Milano
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R11984.pdf

accesso aperto

Dimensione 2.51 MB
Formato Adobe PDF
2.51 MB Adobe PDF Visualizza/Apri

I documenti in UNITESI 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/20.500.14242/74902
Il codice NBN di questa tesi è URN:NBN:IT:UNIMI-74902