×

zbMATH — the first resource for mathematics

Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem. (English) Zbl 1411.90249
Summary: Alternating current optimal power flow (AC OPF) is one of the most fundamental optimization problems in electrical power systems. It can be formulated as a semidefinite program (SDP) with rank constraints. Solving AC OPF, that is, obtaining near optimal primal solutions as well as high quality dual bounds for this non-convex program, presents a major computational challenge to today’s power industry for the real-time operation of large-scale power grids. In this paper, we propose a new technique for reformulation of the rank constraints using both principal and non-principal 2-by-2 minors of the involved Hermitian matrix variable and characterize all such minors into three types. We show the equivalence of these minor constraints to the physical constraints of voltage angle differences summing to zero over three- and four-cycles in the power network. We study second-order conic programming (SOCP) relaxations of this minor reformulation and propose strong cutting planes, convex envelopes, and bound tightening techniques to strengthen the resulting SOCP relaxations. We then propose an SOCP-based spatial branch-and-cut method to obtain the global optimum of AC OPF. Extensive computational experiments show that the proposed algorithm significantly outperforms the state-of-the-art SDP-based OPF solver and on a simple personal computer is able to obtain on average a \(0.71\%\) optimality gap in no more than 720 s for the most challenging power system instances in the literature.

MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C90 Applications of mathematical programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Andersen, MS; Hansson, A.; Vandenberghe, L., Reduced-complexity semidefinite relaxations of optimal power flow problems, IEEE Trans. Power Syst., 29, 1855-1863, (2014)
[2] Bai, X.; Wei, H., Semi-definite programming-based method for security-constrained unit commitment with operational and optimal power flow constraints, IET Gener. Transm. Distrib., 3, 182-197, (2009)
[3] Bai, X.; Wei, H.; Fujisawa, K.; Wang, Y., Semidefinite programming for optimal power flow problems, Electr. Power Energy Syst., 30, 383-392, (2008)
[4] Bienstock, D., Chen, C., Muñoz, G.: Outer-product-free sets for polynomial optimization and oracle-based cuts. arXiv preprint arXiv:1610.04604 (2016)
[5] Bienstock, D., Munoz, G.: On linear relaxations of OPF problems. arXiv preprint arXiv:1411.1120 (2014)
[6] Bose, S.; Gayme, DF; Chandy, KM; Low, SH, Quadratically constrained quadratic programs on acyclic graphs with application to power flow, IEEE Trans. Control Netw. Syst., 2, 278-287, (2015) · Zbl 1370.90168
[7] Bose, S., Gayme, D.F., Low, S., Chandy, K.M.: Optimal power flow over tree networks. In: 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1342-1348 (2011)
[8] Bukhsh, WA; Grothey, A.; McKinnon, K.; Trodden, P., Local solutions of optimal power flow, IEEE Trans. Power Syst., 28, 4780-4788, (2013)
[9] Cain, M.B., O’Neill, R.P., Castillo, A.: History of optimal power flow and formulations. http://www.ferc.gov/industries/electric/indus-act/market-planning/opf-papers/acopf-1-history-formulation-testing.pdf (2012)
[10] Carpentier, J., Contributions to the economic dispatch problem, Bull. Soc. Fr. Electr., 8, 431-447, (1962)
[11] Chen, C.; Atamtürk, A.; Oren, SS, Bound tightening for the alternating current optimal power flow problem, IEEE Trans. Power Syst., PP, 1-8, (2015)
[12] Chen, C.; Atamtürk, A.; Oren, SS, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, Math. Program., 165, 549-577, (2017) · Zbl 1380.65102
[13] Coffrin, C., Gordon, D., Scott, P.: NESTA, The NICTA energy system test case archive. arXiv preprint arXiv:1411.0359 (2014)
[14] Coffrin, C.; Hentenryck, P., A linear-programming approximation of AC power flows, INFORMS J. Comput., 26, 718-734, (2014) · Zbl 1304.90051
[15] Coffrin, C.; Hijazi, HL; Hentenryck, P., The QC relaxation: a theoretical and computational study on optimal power flow, IEEE Trans. Power Syst., 31, 3008-3018, (2016)
[16] Coffrin, C.; Hijazi, HL; Hentenryck, P., Strengthening the SDP relaxation of AC power flows with convex envelopes, bound tightening, and valid inequalities, IEEE Trans. Power Syst., 32, 3549-3558, (2017)
[17] Coffrin, C.; Hentenryck, P., A linear-programming approximation of AC power flows, INFORMS J. Comput., 26, 718-734, (2014) · Zbl 1304.90051
[18] Dey, SS; Gupte, A., Analysis of MILP techniques for the pooling problem, Oper. Res., 63, 412-427, (2015) · Zbl 1327.90351
[19] Frank, S.; Steponavice, I.; Rebennack, S., Optimal power flow: a bibliographic survey I—formulations and deterministic methods, Energy Syst., 3, 221-258, (2012)
[20] Frank, S.; Steponavice, I.; Rebennack, S., Optimal power flow: a bibliographic survey II—nondeterministic and hybrid methods, Energy Syst., 3, 259-289, (2012)
[21] Fukuda, M.; Kojima, M.; Murota, K.; Nakata, K., Exploiting sparsity in semidefinite programming via matrix completion I: general framework, SIAM J. Optim., 11, 647-674, (2001) · Zbl 1010.90053
[22] Gupte, A.; Ahmed, S.; Dey, SS; Cheon, M-S, Relaxations and discretizations for the pooling problem, J. Glob. Optim., 67, 631-669, (2017) · Zbl 1392.90117
[23] Hijazi, H., Coffrin, C., Van Hentenryck, P.: Polynomial SDP cuts for optimal power flow. In: 2016 Power Systems Computation Conference (PSCC), pp. 1-7 (June 2016)
[24] Hijazi, H.L., Coffrin, C., Van Hentenryck, P.: Convex quadratic relaxations of mixed-integer nonlinear programs in power systems. Technical Report, NICTA, Canberra, ACT Australia (2013) · Zbl 1387.90158
[25] Hillestad, RJ; Jacobsen, SE, Linear programs with an additional reverse convex constraint, Appl. Math. Optim., 6, 257-269, (1980) · Zbl 0435.90065
[26] Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013) · Zbl 1267.15001
[27] Jabr, RA, Radial distribution load flow using conic programming, IEEE Trans. Power Syst., 21, 1458-1459, (2006)
[28] Jabr, RA, Optimal power flow using an extended conic quadratic formulation, IEEE Trans. Power Syst., 23, 1000-1008, (2008)
[29] Jabr, RA, Exploiting sparsity in SDP relaxations of the OPF problem, IEEE Trans. Power Syst., 27, 1138-1139, (2012)
[30] Jabr, RA; Coonick, AH; Cory, BJ, A primal-dual interior point method for optimal power flow dispatching, IEEE Trans. Power Syst., 17, 654-662, (2002)
[31] Josz, C.; Maeght, J.; Panciatici, P.; Gilbert, JC, Application of the moment-sos approach to global optimization of the OPF problem, IEEE Trans. Power Syst., 30, 463-470, (2015)
[32] Kocuk, B.: Global Optimization Methods for Optimal Power Flow and Transmission Switching Problems in Electric Power Systems. PhD thesis, Georgia Institute of Technology (2016)
[33] Kocuk, B.; Dey, SS; Sun, XA, Strong SOCP relaxations for the optimal power flow problem, Oper. Res., 64, 1176-1196, (2016) · Zbl 1354.90154
[34] Kocuk, B.; Dey, SS; Sun, XA, Inexactness of SDP relaxation and valid inequalities for optimal power flow, IEEE Trans. Power Syst., 31, 642-651, (2016)
[35] Lavaei, J.; Low, SH, Zero duality gap in optimal power flow problem, IEEE Trans. Power Syst., 27, 92-107, (2012)
[36] Madani, R., Ashraphijuo, M., Lavaei, J.: OPF Solver Guide (2014). http://ieor.berkeley.edu/ lavaei/Software.html
[37] Madani, R., Ashraphijuo, M., Lavaei, J.: Promises of conic relaxation for contingency-constrained optimal power flow problem. Allerton (2014)
[38] Madani, R., Sojoudi, S., Lavaei, J.: Convex relaxation for optimal power flowproblem: Mesh networks. In: Asilomar Conference on Signals, Systems, and Computers (ACSSC), pp. 1375-1382 (2013)
[39] Madani, R.; Sojoudi, S.; Lavaei, J., Convex relaxation for optimal power flow problem: Mesh networks, IEEE Trans. Power Syst., 30, 199-211, (2015)
[40] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[41] Misener, R.; Thompson, JP; Floudas, CA, Apogee: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes, Comput. Chem. Eng., 35, 876-892, (2011)
[42] Molzahn, DK; Hiskens, IA, Sparsity-exploiting moment-based relaxations of the optimal power flow problem, IEEE Trans. Power Syst., 30, 3168-3180, (2015)
[43] Molzahn, DK; Holzer, JT; Lesieutre, BC; DeMarco, CL, Implementation of a large-scale optimal power flow solver based on semidefinite programming, IEEE Trans. Power Syst., 28, 3987-3998, (2013)
[44] Momoh, JA; El-Hawary, ME; Adapa, R., A review of selected optimal power flow literature to 1993 part I: nonlinear and quadratic programming approaches, IEEE Trans. Power Syst., 14, 96-104, (1999)
[45] Momoh, JA; El-Hawary, ME; Adapa, R., A review of selected optimal power flow literature to 1993 part II: Newton, linear programming and interior point methods, IEEE Trans. Power Syst., 14, 105-111, (1999)
[46] MOSEK ApS. MOSEK Optimizer API for .NET manual. Version 8.1 (2017)
[47] Nakata, K.; Fujisawa, K.; Fukuda, M.; Kojima, M.; Murota, K., Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results, Math. Program., 95, 303-327, (2003) · Zbl 1030.90081
[48] Nesterov, Y.; Wolkowicz, H.; Ye, Y.; Wolkowicz, H. (ed.); Saigal, R. (ed.); Vandenberghe, L. (ed.), Semidefinite programming relaxations of nonconvex quadratic optimization, No. 27, 361-419, (2000), Boston · Zbl 0957.90528
[49] Phan, DT, Lagrangian duality and branch-and-bound algorithms for optimal power flow, Oper. Res., 60, 275-285, (2012) · Zbl 1251.90308
[50] Qualizza, A.; Belotti, P.; Margot, F.; Lee, J. (ed.); Leyffer, S. (ed.), Linear programming relaxations of quadratically constrained quadratic programs, 407-426, (2012), New York · Zbl 1242.90155
[51] Sojoudi, S., Lavaei, J.: Physics of power networks makes hard optimization problems easy to solve. In: IEEE Power and Energy Society General Meeting, pp. 1-8 (2012)
[52] Tawarmalani, M., Richard, JP.P.: Decomposition Techniques in Convexification of Inequalities. Technical Report. Working paper (2013)
[53] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, vol. 65. Springer, New York (2002) · Zbl 1031.90022
[54] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[55] Taylor, J.A.: Convex Optimization of Power Systems. Cambridge University Press, Cambridge (2015)
[56] Torres, GL; Quintana, VH, An interior-point method for nonlinear optimal power flow using voltage rectangular coordinates, IEEE Trans. Power Syst., 13, 1211-1218, (1998)
[57] Wang, H.; Murillo-Sánchez, CE; Zimmerman, RD; Thomas, RJ, On computational issues of market based optimal power flow, IEEE Trans. Power Syst., 22, 1185-1193, (2007)
[58] Wu, Y.; Debs, AS; Marsten, RE, A direct nonlinear predictor-corrector primal-dual interior point algorithm for optimal power flows, IEEE Trans. Power Syst., 9, 876-883, (1994)
[59] Zhang, B., Tse, D.: Geometry of feasible injection region of power networks. In: 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1508-1515 (Sept 2011)
[60] Zimmerman, RD; Murillo-Sanchez, CE; Thomas, RJ, MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education, IEEE Trans. Power Syst., 26, 12-19, (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.