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.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.
https://hdl.handle.net/20.500.14242/74902
URN:NBN:IT:UNIMI-74902