We propose a revision of the classical column generation algorithm for solving Dantzig-Wolfe decompositionsof mixed integer programs. It is meant to fully exploit the availability of distributed computing resources,making optimization algorithms in general purpose solvers to scale better.The main idea is to trigger massive parallelism by fully decoupling the computing flow of each component,including the resolution of the master problem, thus allowing different pricing algorithms to concurrently workon different sets of dual variables, and the master algorithm to asynchronously update dual information assoon as new columns are available.Our algorithms ensure the same optimality convergency properties of the classical method. Experiments onmixed integer programs for three benchmark problems from the combinatorial optimization literature proveour approach to be one order of magnitude faster than state-of-the-art general purpose solvers in computinghigh quality root node dual bounds. Even if devised to exploit clusters of machines which do not sharememory space, our algorithms show to be faster than earlier attempts from the literature also when run onvirtual machines hosted on a single physical one, proving this improvement to derive from our algorithmicmethodology rather than technological factors.

Distributed asynchronous column generation / S. Basso, A. Ceselli. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 146:(2022 Oct), pp. 105894.1-105894.16. [10.1016/j.cor.2022.105894]

Distributed asynchronous column generation

S. Basso
Primo
;
A. Ceselli
Ultimo
2022

Abstract

We propose a revision of the classical column generation algorithm for solving Dantzig-Wolfe decompositionsof mixed integer programs. It is meant to fully exploit the availability of distributed computing resources,making optimization algorithms in general purpose solvers to scale better.The main idea is to trigger massive parallelism by fully decoupling the computing flow of each component,including the resolution of the master problem, thus allowing different pricing algorithms to concurrently workon different sets of dual variables, and the master algorithm to asynchronously update dual information assoon as new columns are available.Our algorithms ensure the same optimality convergency properties of the classical method. Experiments onmixed integer programs for three benchmark problems from the combinatorial optimization literature proveour approach to be one order of magnitude faster than state-of-the-art general purpose solvers in computinghigh quality root node dual bounds. Even if devised to exploit clusters of machines which do not sharememory space, our algorithms show to be faster than earlier attempts from the literature also when run onvirtual machines hosted on a single physical one, proving this improvement to derive from our algorithmicmethodology rather than technological factors.
Dantzig-Wolfe decomposition; Column generation; Distributed computing;
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
PSRL217GHAUS_01 - Piano di Sostegno alla Ricerca 2015-2017 - Linea 2 "Dotazione annuale per attività istituzionali" (anno 2017) - HAUS, GOFFREDO MARIA - PSR_LINEA2_ / Piano di sviluppo di ricerca - Dotazioni dipartimentali - Linea 2 - 2017
Article (author)
File in questo prodotto:
File Dimensione Formato  
Distributed_Asynchronous_Column_Generation__Revised_ (3).pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF Visualizza/Apri
1-s2.0-S0305054822001587-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 957.67 kB
Formato Adobe PDF
957.67 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/937307
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact