Distributed Dantzig-Wolfe Decomposition

Mohamed El Tonbari, Shabbir Ahmed

Published 2019-05-08Version 1

Dantzig-Wolfe decomposition (DWD) is a classical algorithm for solving large-scale linear programs whose constraint matrix involves a set of independent blocks coupled with a set of linking rows. The algorithm decomposes such a problem into a master problem and a set of independent subproblems that can be solved in a distributed manner. In a typical implementation, the master problem is solved centrally. In certain settings, solving the master problem centrally is undesirable or infeasible. For example, in the case of decentralized storage of data, or when independent agents who are responsible for the subproblems desire privacy of information. In this paper, we propose a fully distributed DWD algorithm that relies on solving the master problem using a distributed consensus-based Alternating Direction Method of Multipliers (ADMM) algorithm. We derive error bounds on the optimality gap and feasibility violation of the proposed approach. We provide preliminary computational results for our algorithm using a Message Passing Interface (MPI) implementation on randomly generated instances where we obtain high quality solutions.