Decentralized decomposition algorithms for peer-to-peer linear optimization
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1835-1861.

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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019097
Classification : 90C05, 90C06
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2019097/

[1] M. Albrecht and H. Stadtler, Coordinating decentralized linear programs by exchange of primal information, Eur. J. Oper. Res. 247 (2015) 788–796. | DOI | MR

[2] A. Ali and J.L. Kennington, 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] J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962) 238–252. | DOI | MR | Zbl

[4] S.P. Bradley, A.C. Hax and T.L. Magnanti, Applied Mathematical Programming. Addison-Wesley Publishing Company, Reading, MA (1977).

[5] M. Bürger, G. Notarstefano and F. Allgöwer, Locally constrained decision making via two-stage distributed simplex. In: Decision and Control and European Control Conference (CDC-ECC) (2011) 5911–5916. | DOI

[6] G. Dantzig, Linear Programming and Extensions. Princeton Landmarks in Mathematics and Physics. Princeton University Press (2016). | MR | Zbl

[7] G.B. Dantzig and M.N. Thapa, Linear programming: 2: Theory and Extensions. Springer Science & Business Media (2006). | Zbl

[8] G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Oper. Res. 8 (1960) 101–111. | DOI | Zbl

[9] H. Dutta and H. Kargupta, Distributed linear programming and resource management for data mining in distributed environments. In: IEEE International Conference on Data Mining Workshops (2008) 543–552.

[10] Y. Hong, J. Vaidya and H. Lu, Secure and efficient distributed linear programming, J. Comput. Secur. 20 (2012) 583–634. | DOI

[11] I.-J. Jeong and V. Jorge Leon, 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] E. Kalvelagen, Column Generation with Gams. Gams Development Corp., Washinton, DC (2003).

[13] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395. | DOI | MR | Zbl

[14] S.Y.P. Lu, H.Y.K. Lau and C.K.F. Yiu, A hybrid solution to collaborative decision-making in a decentralized supply-chain, J. Eng. Technol. Manage. 29 (2012) 95–111. | DOI

[15] R.K. Martin, 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] Y. Pochet and L.A. Wolsey, 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] J.B. Rosen, Primal partition programming for block diagonal matrices, Numer. Math. 6 (1964) 250–260. | DOI | MR | Zbl

[19] S. Schleicher, Decentralized optimization of linear economic systems with minimum information exchange of the subsystems, Z. Nationalökonomie 31 (1971) 33–44. | DOI

[20] S.J. Stoyan, M.M. Dessouky and X. Wang, Introduction to large scale linear programming and applications. In: Wiley Encyclopedia of Operations Research and Management Science (2010).

[21] Z.C. Taşkn, Benders decomposition. In: Wiley Encyclopedia of Operations Research and Management Science (2010).

[22] Z.C. Taşkn, S. Ağral, A. Tamer Unal, V. Belada and F. Gokten-Yilmaz, Mathematical programming-based sales and operations planning at Vestel Electronics, Interfaces 45 (2015) 325–340. | DOI

Cité par Sources :