Distributed asynchronous column generation. (October 2022)

• Record Type: Journal Article
• Authors: Basso, Saverio; Ceselli, Alberto
• Is Part Of: Computers & operations research. Volume 146(2022)
• Publication Date: 2022-10
• Subjects: Dantzig–Wolfe decomposition -- Column generation -- Distributed computing; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105894
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We propose a revision of the classical column generation algorithm for solving Dantzig–Wolfe decompositions of 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 work on different sets of dual variables, and the master algorithm to asynchronously update dual information as soon as new columns are available. Our algorithms ensure the same optimality convergency properties of the classical method. Experiments on mixed integer programs for three benchmark problems from the combinatorial optimization literature prove our approach to be one order of magnitude faster than state-of-the-art general purpose solvers in computing high quality root node dual bounds. Even if devised to exploit clusters of machines which do not share memory space, our algorithms show to be faster than earlier attempts from the literature also when run on virtual machines hosted on a single physical one, proving this improvement to derive from our algorithmic methodology rather than technological factors. Highlights: We revise column generation algorithms for Dantzig–Wolfe decompositions of MIPs. We trigger massive parallelism by fully decoupling computing flows of each component. We design an architecture and a set of policies to exploit distributed computing. We experiment on MIPs for three combinatorial optimization benchmark problems. Experiments indicate our approach to strongly improve scalability on decomposable MIPs.