A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 6 Issue 5
Sep.  2019

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 6.171, Top 11% (SCI Q1)
    CiteScore: 11.2, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
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

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

doi: 10.1109/JAS.2019.1911705
Funds:  This work was supported by National Science Foundation award ECCS-1653838
More Information
  • 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.

     

  • loading
  • 1Resources are generically categorized as CPUs (number of independent computational units), primary storage (amount of memory/RAM), secondary storage (disk, cloud, etc.).
    2An articulation point of an undirected connected graph is a node whose removal along with its incident edges disconnects the graph [32].
  • [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

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(6)

    Article Metrics

    Article views (1450) PDF downloads(43) Cited by()

    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.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return