We propose Decentralized Benders Decomposition and Decentralized Dantzig–Wolfe Decomposition algorithms for large-scale block angular linear programming problems. Our methods allow multiple peer decision makers to cooperate with the aim of solving the problem without the need of a central coordination mechanism. Instead we achieve cooperation by partial information sharing across a strongly connected communication network. Our main goal is to design decentralized solution approaches for decision makers who are unwilling to disclose their local data, but want to solve the global problem collaboratively for mutual benefit. We prove that our proposed methods reach global optimality in a finite number of iterations. We confirm our theoretical results with computational experiments.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019097
Mots-clés : Linear programming, decentralized coordination, peer-to-peer optimization, block angular structure
@article{RO_2020__54_6_1835_0,
author = {Aydin, M. Asli and Ta\c{s}kin, Z. Caner},
title = {Decentralized decomposition algorithms for peer-to-peer linear optimization},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1835--1861},
publisher = {EDP-Sciences},
volume = {54},
number = {6},
year = {2020},
doi = {10.1051/ro/2019097},
mrnumber = {4150231},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2019097/}
}
TY - JOUR AU - Aydin, M. Asli AU - Taşkin, Z. Caner TI - Decentralized decomposition algorithms for peer-to-peer linear optimization JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2020 SP - 1835 EP - 1861 VL - 54 IS - 6 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2019097/ DO - 10.1051/ro/2019097 LA - en ID - RO_2020__54_6_1835_0 ER -
%0 Journal Article %A Aydin, M. Asli %A Taşkin, Z. Caner %T Decentralized decomposition algorithms for peer-to-peer linear optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2020 %P 1835-1861 %V 54 %N 6 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2019097/ %R 10.1051/ro/2019097 %G en %F RO_2020__54_6_1835_0
Aydin, M. Asli; Taşkin, Z. Caner. Decentralized decomposition algorithms for peer-to-peer linear optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1835-1861. doi : 10.1051/ro/2019097. http://archive.numdam.org/articles/10.1051/ro/2019097/
[1] and , Coordinating decentralized linear programs by exchange of primal information, Eur. J. Oper. Res. 247 (2015) 788–796. | DOI | MR
[2] and , Mnetgen program documentation. Technical report, Department of Industrial Engineering and Operations Research. Technical report, Department of Industrial Engineering and Operations Research, Southern Methodist University, Dallas, TX (1977).
[3] , Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962) 238–252. | DOI | MR | Zbl
[4] , and , Applied Mathematical Programming. Addison-Wesley Publishing Company, Reading, MA (1977).
[5] , and , Locally constrained decision making via two-stage distributed simplex. In: Decision and Control and European Control Conference (CDC-ECC) (2011) 5911–5916. | DOI
[6] , Linear Programming and Extensions. Princeton Landmarks in Mathematics and Physics. Princeton University Press (2016). | MR | Zbl
[7] and , Linear programming: 2: Theory and Extensions. Springer Science & Business Media (2006). | Zbl
[8] and , Decomposition principle for linear programs, Oper. Res. 8 (1960) 101–111. | DOI | Zbl
[9] and , Distributed linear programming and resource management for data mining in distributed environments. In: IEEE International Conference on Data Mining Workshops (2008) 543–552.
[10] , and , Secure and efficient distributed linear programming, J. Comput. Secur. 20 (2012) 583–634. | DOI
[11] and , Distributed allocation of the capacity of a single-facility using cooperative interaction via coupling agents, Int. J. Prod. Res. 41 (2003) 15–30. | DOI | Zbl
[12] , Column Generation with Gams. Gams Development Corp., Washinton, DC (2003).
[13] , A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395. | DOI | MR | Zbl
[14] , and , A hybrid solution to collaborative decision-making in a decentralized supply-chain, J. Eng. Technol. Manage. 29 (2012) 95–111. | DOI
[15] , Large Scale Linear and Integer Optimization: A Unified Approach. Springer, US (2012). | MR | Zbl
[16] Multicommodity problems. Available from: http://www.di.unipi.it/optimize/Data/MMCF.html (2020).
[17] and , Production Planning by Mixed Integer Programming. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York Inc, Secaucus, NJ, USA (2006). | MR | Zbl
[18] , Primal partition programming for block diagonal matrices, Numer. Math. 6 (1964) 250–260. | DOI | MR | Zbl
[19] , Decentralized optimization of linear economic systems with minimum information exchange of the subsystems, Z. Nationalökonomie 31 (1971) 33–44. | DOI
[20] , and , Introduction to large scale linear programming and applications. In: Wiley Encyclopedia of Operations Research and Management Science (2010).
[21] , Benders decomposition. In: Wiley Encyclopedia of Operations Research and Management Science (2010).
[22] , , , and , Mathematical programming-based sales and operations planning at Vestel Electronics, Interfaces 45 (2015) 325–340. | DOI
Cité par Sources :
