The complexity of most power grid simulation algorithms scales with the network size, which corresponds to the number of buses and branches in the grid. Parallel and distributed computing is one approach that can be used to achieve improved scalability. However, the efficiency of these algorithms requires an optimal grid partitioning strategy. To obtain the requisite power grid partitionings, the authors first apply several graph theory based partitioning algorithms, such as the Karlsruhe fast flow partitioner (KaFFPa), spectral clustering, and METIS. The goal of this study is an examination and evaluation of the impact of grid partitioning on power system problems. To this end, the computational performance of AC optimal power flow (OPF) and dynamic power grid simulation are tested. The partitioned OPF-problem is solved using the augmented Lagrangian based alternating direction inexact Newton method, whose solution is the basis for the initialisation step in the partitioned dynamic simulation problem. The computational performance of the partitioned systems in the implemented parallel and distributed algorithms is tested using various IEEE standard benchmark test networks. KaFFPa not only outperforms other partitioning algorithms for the AC OPF problem, but also for dynamic power grid simulation with respect to computational speed and scalability.

References

1. 1)
  - 31. Holtgrewe, M., Sanders, P., Schulz, C.: ‘Engineering a scalable high quality graph partitioner’. 2010 IEEE Int. Symp. on Parallel & Distributed Processing, Atlanta, GA, USA, April 2010.
2. 2)
  - 16. Schlag, S., Henne, V., Heuer, T., et al: ‘k-way hypergraph partitioning via n-level recursive bisection’. 2016 Proc. of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Arlington, Virginia, USA, 2016, pp. 53–67.
3. 3)
  - 12. Ilic'-Spong, M., Crow, M.L., Pai, M.A.: ‘Transient stability simulation by waveform relaxation methods’, IEEE Trans. Power Syst., 1987, 2, (4), pp. 943–952.
4. 4)
  - 14. Ng, A.Y., Jordan, M.I., Weiss, Y.: ‘On spectral clustering: analysis and an algorithm’. 14th Int. Conf. on Neural Information Processing Systems: Natural and Synthetic, Vancouver, British Columbia, Canada, 2001.
5. 5)
  - 10. Decker, I., Falcao, D., Kaszkurewicz, E.: ‘An efficient parallel method for transient stability analysis’. Proc. of the Tenth Power Systems Computation Conf., Graz, Austria, 1990.
6. 6)
  - 28. Sanders, P., Schulz, C.: ‘Think locally, act globally: highly balanced graph partitioning’, in Vincenzo, Bonifaci, Camil, Demetrescu, Alberto, Marchetti-Spaccamela (Eds.): ‘Experimental algorithms’ (Springer, Berlin Heidelberg, 2013), pp. 164–175.
7. 7)
  - 41. Kyesswa, M., Çakmak, H.K., Kühnapfel, U., et al: ‘A matlab-based simulation tool for the analysis of unsymmetrical power system transients in large networks’. European Conf. on Modelling and Simulation (ECMS), Wilhelmshaven, Germany, May 2018.
8. 8)
  - 38. Murray, A., Kyesswa, M., Schmurr, P., et al: ‘On grid partitioning in AC optimal power flow’. Accepted at 2020 IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe), The Hague, the Netherlands, October 2020.
9. 9)
  - 20. Kyesswa, M., Çakmak, H., Kühnapfel, U., et al: ‘A matlab-based dynamic simulation module for power system transients analysis in the eASiMOV framework’. European Modelling Symp., Manchester, UK, November 2017.
10. 10)
  - 40. Wächter, A., Biegler, L.: ‘On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming’, Math. Program., 2005, 106, (1), pp. 25–57.
11. 11)
  - 13. Hou, L., Bose, A.: ‘Implementation of the waveform relaxation algorithm on a shared memory computer for the transient stability problem’, IEEE Trans. Power Syst., 1997, 12, (3), pp. 1053–1060.
12. 12)
  - 37. Zimmerman, R.D., Murillo-Sanchez, C.E., Thomas, R.J.: ‘MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education’, IEEE Trans. Power Syst., 2011, 26, (1), pp. 12–19.
13. 13)
  - 8. Murray, A., Engelmann, A., Hagenmeyer, V.: ‘Hierarchical distributed mixed-integer optimization for reactive power dispatch’. 10th Symp. on Control of Power and Energy Systems, Tokyo, Japan, 2018.
14. 14)
  - 6. Tomim, M., Martí, J., Wang, L.: ‘Parallel solution of large power system networks using the multi-area Thévenin equivalents (MATE) algorithm’, Int. J. Electr. Power Energy Syst., 2009, 31, (9), pp. 497–503.
15. 15)
  - 7. Liu, J., Benosman, M., Raghunathan, A.U.: ‘Consensus-based distributed optimal power flow algorithm’. 2015 IEEE Power Energy Society Innovative Smart Grid Technologies Conf. (ISGT), Washington, DC, USA, February 2015.
16. 16)
  - 36. Josz, C., Fliscounakis, S., Maeght, J., et al: ‘AC power flow data in MATPOWER and QCQP format: iTesla, RTE Snapshots, and PEGASE’, 2016. Available at http://arxiv.org/abs/1603.01533.
17. 17)
  - 24. Engelmann, A., Mühlpfordt, T., Jiang, Y., et al: ‘Distributed AC optimal power flow using ALADIN’, IFAC-PapersOnLine, 2017, 50, (1), pp. 5536–5541.
18. 18)
  - 17. Drechsler, R., Gunther, W., Eschbach, T., et al: ‘Recursive bi-partitioning of netlists for large number of partitions’, Euromicro Symp. Digital Syst. Design, 2002, 2002, pp. 38–44.
19. 19)
  - 26. Crow, M.L.: ‘Computational methods for electric power systems’ (CRC Press, Boca Raton, FL, USA, 2009).
20. 20)
  - 23. Kyesswa, M., Çakmak, H., Kühnapfel, U., et al: ‘Generator model extension for higher accuracy simulation of power system transients in OpenModelica’. MCSI, Corfu, Greece, 2017.
21. 21)
  - 32. Sanders, P., Schulz, C.: ‘High quality graph partitioning’. 10th DIMACS implementation challenge workshop: Graph Partitioning and Graph Clustering, Atlanta, GA, USA, 2013.
22. 22)
  - 19. Houska, B., Frasch, J., Diehl, M.: ‘An augmented Lagrangian based algorithm for distributed nonConvex optimization’, SIAM J. Optim., 2016, 26, (2), pp. 1101–1127.
23. 23)
  - 27. Kyesswa, M., Schmurr, P., Çakmak, H.K., et al: ‘A new julia-based parallel time-domain simulation algorithm for analysis of power system dynamics’. 2020 IEEE/ACM 24th Int. Symp. on Distributed Simulation and Real Time Applications (DS-RT), Prague, Czech Republic, September 2020.
24. 24)
  - 15. Guo, J., Hug, G., Tonguz, O.K.: ‘Intelligent partitioning in distributed optimization of electric power systems’, IEEE Trans. Smart Grid, 2016, 7, (3), pp. 1249–1258.
25. 25)
  - 1. Frank, S., Steponavice, I., Rebennack, S.: ‘Optimal power flow: a bibliographic survey, I: formulations and deterministic methods’, Energy Syst., 2012, 3, pp. 221–258.
26. 26)
  - 21. IEEEStd 421.5-2005: ‘IEEE recommended practice for excitation system models for power system stability studies’ (IEEE, NewYork, 2006).
27. 27)
  - 30. Maue, J., Sanders, P.: ‘Engineering algorithms for approximate weighted matching’. Int. Workshop on Experimental and Efficient Algorithms, Rome, Italy, 2007.
28. 28)
  - 35. ‘Power systems test case archive - UWEE’,. Available at https://www2.ee.washington.edu/research/pstca/, accessed 11 June 2018.
29. 29)
  - 25. Boyd, S., Vandenberghe, L.: ‘Convex optimization’ (Cambridge university press, New York, USA, 2004).
30. 30)
  - 22. Task Force on Turbine-Governor Modeling: ‘Dynamic models for turbine-governors in power system studies’ (IEEE Power & Energy Society, USA, 2013).
31. 31)
  - 2. Frank, S., Steponavice, I., Rebennack, S.: ‘Optimal power flow: a bibliographic survey, II: nondeterministic and hybrid methods’, Energy Syst., 2013, 3, pp. 259–289.
32. 32)
  - 18. Buluç, A., Meyerhenke, H., Safro, I., et al: ‘Recent advances in graph partitioning’, in Lasse, Kliemann, Peter, Sanders (Eds.): ‘Algorithm engineering’ (Springer, Cham, Switzerland, 2016), pp. 117–158.
33. 33)
  - 11. Scala, M.L., Sbrizzai, R., Torelli, F.: ‘A pipelined-in-time parallel algorithm for transient stability analysis’, IEEE Trans. Power Syst., 1991, 6, (2), pp. 715–722.
34. 34)
  - 3. Koester, D., Ranka, S., Fox, G.: ‘Power systems transient stability-a grand computing challenge’, Northeast Parallel Architectures Center, Syracuse, NY, Tech. Rep. SCCS, vol. 549, 1992.
35. 35)
  - 4. D'Arco, S., Suul, J.A., Fosso, O.B.: ‘A virtual synchronous machine implementation for distributed control of power converters in smartgrids’, Electr. Power Syst. Res., 2015, 122, pp. 180–197.
36. 36)
  - 39. Engelmann, A., Jiang, Y., Houska und T. Faulwasser, B.: ‘Decomposition of non-convex optimization via bi-level distributed ALADIN’, arXiv: Available at https://arxiv.org/abs/1903.11280.
37. 37)
  - 9. Low, S.H.: ‘Convex relaxation of optimal power flow–part II: exactness’, IEEE Trans. Control Netw. Syst., 2014, 1, (2), pp. 177–189.
38. 38)
  - 29. Sanders, P., Schulz, C.: ‘Engineering multilevel graph partitioning algorithms’. 19th European Symp. on Algorithms, Saarbrücken, Germany, 2011.
39. 39)
  - 33. Karypis, G.: ‘METIS: a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices version 5.1.0’ (University of Minnesota, Department of Computer Science & Engineering, Minneapolis, MN, USA, March 2013).
40. 40)
  - 5. Pellegrini, F.: ‘Distillating knowledge about SCOTCH’, in Uwe, Naumann, Horst, D. Simon (Eds.): ‘Combinatorial scientific computing (Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009), pp. 1–12.
41. 41)
  - 34. Bezanson, J., Edelman, A., Karpinski, S., et al: ‘Julia: a fresh approach to numerical computing’, SIAM Rev., 2017, 59, (1), pp. 65–98.

Impact of grid partitioning algorithms on combined distributed AC optimal power flow and parallel dynamic power grid simulation

References

Related content