Optimization Online


Distributed Dantzig-Wolfe Decomposition

Mohamed El Tonbari (mtonbari***at***gatech.edu)
Shabbir Ahmed (shabbir.ahmed***at***isye.gatech.edu)

Abstract: 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.

Keywords: column generation, distributed optimization, consensus algorithm

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 05/08/2019
Entry Accepted: 05/08/2019
Entry Last Modified: 05/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society