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 / S. Basso ; tutor: A. Ceselli ; coordinator: P. Boldi. - : . Dipartimento di Informatica Giovanni Degli Antoni, 2021 Mar 22. ((33. ciclo, Anno Accademico 2020. [10.13130/basso-saverio_phd2021-03-22].

DATA DRIVEN ALGORITHMS AND DISTRIBUTED COMPUTING FOR AUTOMATIC MIP DECOMPOSITIONS

S. Basso
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.
CESELLI, ALBERTO
BOLDI, PAOLO
Mathematical Programming; Machine Learning; Distributed Computing; Dantzig-Wolfe decomposition; Column Generation
Settore INF/01 - Informatica
DATA DRIVEN ALGORITHMS AND DISTRIBUTED COMPUTING FOR AUTOMATIC MIP DECOMPOSITIONS / S. Basso ; tutor: A. Ceselli ; coordinator: P. Boldi. - : . Dipartimento di Informatica Giovanni Degli Antoni, 2021 Mar 22. ((33. ciclo, Anno Accademico 2020. [10.13130/basso-saverio_phd2021-03-22].
Doctoral Thesis
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R11984.pdf

accesso aperto

Tipologia: Tesi di dottorato completa
Dimensione 2.51 MB
Formato Adobe PDF
2.51 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS 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/2434/820203
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact