Consensus-based Dantzig-Wolfe decomposition

Mohamed El Tonbari and Shabbir Ahmed

European Journal of Operational Research, 2023, vol. 307, issue 3, 1441-1456

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 model 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, such as 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 which relies on solving the master problem using a consensus-based Alternating Direction Method of Multipliers (ADMM) method. 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 implementation on a delivery planning problem, the multi-commodity network flow problem, and synthetic instances where we obtain high quality solutions. An open-source implementation of the algorithm is available.

Keywords: Distributed decision making; Dantzig Wolfe decomposition; Column generation; Privacy; Decentralized data storage (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722008074
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:307:y:2023:i:3:p:1441-1456

DOI: 10.1016/j.ejor.2022.10.019

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().