Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions

Reza Asadi; Solmaz S. Kia

doi:10.1109/JAS.2019.1911705

Volume 6 Issue 5

Sep. 2019

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2019 > 6(5): 1251-1260

Reza Asadi and Solmaz S. Kia, "Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions," IEEE/CAA J. Autom. Sinica, vol. 6, no. 5, pp. 1251-1260, Sept. 2019. doi: 10.1109/JAS.2019.1911705

Citation:

Reza Asadi and Solmaz S. Kia, "Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions," IEEE/CAA J. Autom. Sinica, vol. 6, no. 5, pp. 1251-1260, Sept. 2019. doi: 10.1109/JAS.2019.1911705

Citation:

PDF( 878 KB)

Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions

doi: 10.1109/JAS.2019.1911705

Reza Asadi^,,
Solmaz S. Kia

Funds: This work was supported by National Science Foundation award ECCS-1653838

More Information

Author Bio:
Reza Asadi is with the Department of Computer Science at University of California, Irvine. He received the B.Sc. and M.Sc. degrees in computer science from Amirkabir University of Technology, Iran, in 2011 and 2013, respectively. His main research interests are in broad areas of distributed optimization and machine learning. His research focuses on developing scalable optimization and machine learning algorithms for large scale problems

Solmaz S. Kia is with the Department of Mechanical and Aerospace Engineering, University of California, Irvine (UCI). She obtained the Ph.D. degree in mechanical and aerospace engineering from UCI, in 2009, and the M.Sc. and B.Sc. degrees in aerospace engineering from the Sharif University of Technology, Iran, in 2004 and 2001, respectively. She was a Senior Research Engineer at SySense Inc., El Segundo, CA from Jun. 2009-Sep. 2010. She held postdoctoral positions in the Department of Mechanical and Aerospace Engineering at the UC San Diego and UCI. She was the recipient of UC President’s Postdoctoral Fellowship from 2012-2014. She is also a recipient of 2017 NSF CAREER award. Dr. Kia’s main research interests, in a broad sense, include nonlinear control theory, distributed optimization/coordination/estimation, and probabilistic robotics
Corresponding author: Reza Asadi is with the Computer Science Department, University of California, Irvine, CA 92697 USA (e-mail: rasadi@uci.edu)
¹Resources are generically categorized as CPUs (number of independent computational units), primary storage (amount of memory/RAM), secondary storage (disk, cloud, etc.).
²An articulation point of an undirected connected graph is a node whose removal along with its incident edges disconnects the graph [32].
Received Date: 2019-05-06
Accepted Date: 2019-07-11

Available Online: 2019-07-20

Abstract

Abstract

In this paper, we use the cycle basis from graph theory to reduce the size of the decision variable space of optimal network flow problems by eliminating the aggregated flow conservation constraint. We use a minimum cost flow problem and an optimal power flow problem with generation and storage at the nodes to demonstrate our decision variable reduction method. The main advantage of the proposed technique is that it retains the natural sparse/decomposable structure of network flow problems. As such, the reformulated problems are still amenable to distributed solutions. We demonstrate this by proposing a distributed alternating direction method of multipliers (ADMM) solution for a minimum cost flow problem. We also show that the communication cost of the distributed ADMM algorithm for our proposed cycle-based formulation of the minimum cost flow problem is lower than that of a distributed ADMM algorithm for the original arc-based formulation.
- ADMM,
- cycle basis,
- distributed optimization,
- optimal network Flow

FullText(HTML)

¹Resources are generically categorized as CPUs (number of independent computational units), primary storage (amount of memory/RAM), secondary storage (disk, cloud, etc.).
²An articulation point of an undirected connected graph is a node whose removal along with its incident edges disconnects the graph [32].

References(36)

References

[1]	D. P. Bertsekas, Network Optimization: Continuous and Discrete Models. Citeseer, 1998.
[2]	K. Qin, C. Huang, N. Ganesan, K. Liu, and X. Chen, " Minimum cost multi-path parallel transmission with delay constraint by extending openflow,” China Communications, vol. 15, no. 3, pp. 15–26, 2018. doi: 10.1109/CC.2018.8331988
[3]	A. Sinha and E. Modiano, " Optimal control for generalized networkflow problems,” IEEE/ACM Transactions on Networking (TON), vol. 26, no. 1, pp. 506–519, 2018. doi: 10.1109/TNET.2017.2783846
[4]	C. Rosdahl, G. Nilsson, and G. Como, " On distributed optimal control of traffic flows in transportation networks,” in Proc. IEEE Conf. on Control Technology and Applications, pp. 903–908, 2018.
[5]	S. Pourazarm and C. G. Cassandras, " Optimal routing of energyaware vehicles in transportation networks with inhomogeneous charging nodes,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 8, pp. 2515–2527, 2018. doi: 10.1109/TITS.2017.2752202
[6]	K. Nakayama, C. Zhao, L. F. Bic, M. B. Dillencourt, and J. Brouwer, " Distributed power flow loss minimization control for future grid,” International Journal of Circuit Theory and Applications, vol. 43, no. 9, pp. 1209–1225, 2015. doi: 10.1002/cta.v43.9
[7]	C. D. Nicholson and W. Zhang, " Optimal network flow: a predictive analytics perspective on the fixed-charge network flow problem,” Computers &Industrial Engineering, vol. 99, pp. 260–268, 2016.
[8]	T. Soares, R. J. Bessa, P. Pinson, and H. Morais, " Active distribution grid management based on robust ac optimal power flow,” IEEE Transactions on Smart Grid, vol. 9, no. 6, pp. 6229–6241, 2018. doi: 10.1109/TSG.2017.2707065
[9]	J. Qin, Y. Chow, J. Yang, and R. Rajagopal, " Distributed online modified greedy algorithm for networked storage operation under uncertainty,” IEEE Transactions on Smart Grid, vol. 7, no. 2, pp. 1106–1118, 2016.
[10]	K. M. Chandy, S. H. Low, U. Topcu, and H. Xu, " A simple optimal power flow model with energy storage,” in Proc. 49th IEEE Conf. on Decision and Control (CDC), pp. 1051–1057, 2010.
[11]	S. Sun, J. A. Taylor, M. Dong, and B. Liang, " Distributed real-time phase balancing for power grids with energy storage,” in Proc. IEEE American Control Conf. (ACC), 2015, pp. 3032–3037.
[12]	J. Lavaei and S. H. Low, " Zero duality gap in optimal power flow problem,” IEEE Transactions on Power Systems, vol. 27, no. 1, pp. 92–107, 2012. doi: 10.1109/TPWRS.2011.2160974
[13]	J. F. Mota, J. M. Xavier, P. M. Aguiar, and M. Püschel, " Distributed optimization with local domains: applications in MPC and network flows,” IEEE Transactions on Automatic Control, vol. 60, no. 7, pp. 2004–2009, 2015. doi: 10.1109/TAC.2014.2365686
[14]	S. Rezaei, K. Kim, and E. Bozorgzadeh, " Scalable multi-queue data transfer scheme for fpga-based multi-accelerators,” in Proc. 2018 IEEE Int. Conf. on Computer Design (ICCD), pp. 374–380.
[15]	A. Billionnet and É. Soutif, " An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem,” European Journal of Operational Research, vol. 157, no. 3, pp. 565–575, 2004. doi: 10.1016/S0377-2217(03)00244-3
[16]	H. Kellerer, U. Pferschy, and D. Pisinger, " Other knapsack problems,” in Knapsack Problems, pp. 389–424, Springer, 2004.
[17]	M. A. Osorio, F. Glover, and P. Hammer, " Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions,” Annals of Operations Research, vol. 117, no. 1-4, pp. 71–93, 2002.
[18]	M. Esmaeili and A. Mosavi, " Notice of retraction variable reduction for multi-objective optimization using data mining techniques; application to aerospace structures,” in Proc. 2nd Int. Conf. Computer Engineering and Technology (ICCET), vol. 5, pp. V5-333.
[19]	G. Wu, W. Pedrycz, H. Li, D. Qiu, M. Ma, and J. Liu, " Complexity reduction in the use of evolutionary algorithms to function optimization: a variable reduction strategy,” The Scientific World Journal, vol. 2013, 2013.
[20]	S. Boyd and L. Vandenberghe, Convex optimization. England, US: CUP, 2004.
[21]	M. T. Heath, " Some extensions of an algorithm for sparse linear least squares problems,” SIAM Journal on Scientific and Statistical Computing, vol. 3, no. 2, pp. 223–237, 1982. doi: 10.1137/0903014
[22]	A. K. Cline and I. S. Dhillon, Computation of the Singular Value Decomposition. CRC Press, 2006.
[23]	M. Khorramizadeh and N. Mahdavi-Amiri, " An efficient algorithm for sparse null space basis problem using abs methods,” Numerical Algorithms, vol. 62, no. 3, pp. 469–485, 2013. doi: 10.1007/s11075-012-9599-1
[24]	Q. Ba, K. Savla, and G. Como, " Distributed optimal equilibrium selection for traffic flow over networks,” in Proc. IEEE Conf. on Decision and Control, 2015.
[25]	Q. Peng and S. H. Low, " Distributed optimal power flow algorithm for radial networks, Ⅰ: Balanced single phase case,” IEEE Transactions on Smart Grid, vol. 9, no. 1, pp. 111–121, 2018. doi: 10.1109/TSG.2016.2546305
[26]	M. P. Abraham and A. A. Kulkarni, " ADMM-Based algorithm for solving DC-OPF in a large electricity network considering transmission losses,” IET Generation,Transmission &Distribution, vol. 12, no. 21, pp. 5811–5823, 2018.
[27]	Y. Zhang, M. Hong, E. Dall’Anese, S. V. Dhople, and Z. Xu, " Distributed controllers seeking ac optimal power flow solutions using ADMM,” IEEE Transactions on Smart Grid, vol. 9, no. 5, pp. 4525–4537, 2018. doi: 10.1109/TSG.5165411
[28]	J. D. Horton, " A polynomial-time algorithm to find the shortest cycle basis of a graph,” SIAM Journal on Computing, vol. 16, no. 2, pp. 358–366, 1987. doi: 10.1137/0216026
[29]	R. Hariharan, T. Kavitha, and K. Mehlhorn, " Faster algorithms for minimum cycle basis in directed graphs,” SIAM Journal of Computing, vol. 38, no. 3, pp. 1430–1447, 2008.
[30]	S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, " Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends ® in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011.
[31]	J. F. Mota, " Communication-Efficient algorithms for distributed optimization,” arXiv preprint arXiv: 1312.0263, 2013.
[32]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. 3th ed, MIT, 2009.
[33]	R. Asadi, S. S. Kia, and A. Regan, " Cycle basis distributed ADMM solution for optimal network flow problem over bi-connected graphs,” in Proc. 54th IEEE Annual Allerton Conf. on Communication, Control, and Computing, pp. 717–723, 2016.
[34]	A. Dharwadker and S. Pirzada, Graph Theory. CreateSpace Independent Publishing Platform, 2011.
[35]	T. Leibfried, T. Mchedlidze, N. Meyer-Hübner, M. Nöllenburg, I. Rutter, P. Sanders, D. Wagner, and F. Wegner, " Operating power grids with few flow control buses,” in Proc. of the 6th ACM Int. Conf. on Future Energy Systems, pp. 289–294, 2015.
[36]	J. Edmonds and R. M. Karp, " Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the ACM , vol. 19, no. 2, pp. 248–264, 1972. doi: 10.1145/321694.321699

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(6)

Get Citation

PDF

XML

Article Metrics

Article views (1727) PDF downloads(49)

Highlights

Cycle basis from graph theory is used to reduce the size of the decision variable space of optimal network flow problem.
Proposed technique retains the natural sparse/decomposable structure of network flow problems.
The reformulated problems are still amenable to distributed solutions.
A cycle based distributed ADMM solution is demonstrated for a minimum cost flow problem.

Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions

doi: 10.1109/JAS.2019.1911705

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content