Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches

References

• Network X. High-productivity software for complex networks, Available at https://networkx.github.io.
   Google Scholar
• T. Achterberg, SCIP: solving constraint integer programs, Math. Programm. Comput. 1 (2009), pp. 1–41. doi: 10.1007/s12532-008-0001-1
   Google Scholar
• C. Analytics, Anaconda, Available at https://www.continuum.io/anaconda-overview.
   Google Scholar
• M.F. Anjos, B. Ghaddar, L. Hupp, F. Liers, and A. Wiegele, Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method, in Facets of Combinatorial Optimization, M. Jünger and G. Reinelt, eds., Springer, Berlin, 2013, pp. 355–386.
   Google Scholar
• D.A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Graph Partitioning and Graph Clustering, Vol. 588, American Mathematical Society, Providence, 2013.
   Google Scholar
• F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res. 36 (1988), pp. 493–513. doi: 10.1287/opre.36.3.493
   Web of Science ®Google Scholar
• F. Barahona and A.R. Mahjoub, On the cut polytope, Math. Program. 36 (1986), pp. 157–173. doi: 10.1007/BF02592023
   Web of Science ®Google Scholar
• J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962), pp. 238–252. doi: 10.1007/BF01386316
   Google Scholar
• M. Bjørndal and K. Jørnsten, Zonal pricing in a deregulated electricity market, Energy J. 22 (2001), pp. 51–73. doi: 10.5547/ISSN0195-6574-EJ-Vol22-No1-3
   Web of Science ®Google Scholar
• M. Bjørndal and K. Jørnsten, Benefits from coordinating congestion management—the nordic power market, Energy Policy 35 (2007), pp. 1978–1991. doi: 10.1016/j.enpol.2006.06.014
   Web of Science ®Google Scholar
• J.F. Bonnans, J.C. Gilbert, C. Lemaréchal, and C.A. Sagastizábal, Numerical Optimization. Theoretical and Practical Aspects, Springer Science & Business Media, Berlin, 2006.
   Google Scholar
• E. Boros and P.L. Hammer, The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds, Ann. Oper. Res. 33 (1991), pp. 151–180. doi: 10.1007/BF02115753
   Google Scholar
• J. Boucher and Y. Smeers, Alternative models of restructured electricity systems, part 1: No market power, Oper. Res. 49 (2001), pp. 821–838. doi: 10.1287/opre.49.6.821.10017
   Web of Science ®Google Scholar
• C. Breuer and A. Moser, Optimized bidding area delimitations and their impact on electricity markets and congestion management, 11th International Conference on the European Energy Market (EEM14), Krakow, Poland, 2014, pp. 1–5.
   Google Scholar
• R. Carvajal, M. Constantino, M. Goycoolea, J.P. Vielma, and A. Weintraub, Imposing connectivity constraints in forest planning models, Oper. Res. 61 (2013), pp. 824–836. doi: 10.1287/opre.2013.1183
   Web of Science ®Google Scholar
• H.P. Chao and S.C. Peck, Reliability management in competitive electricity markets, J. Regul. Econ. 14 (1998), pp. 189–200. doi: 10.1023/A:1008061319181
   Web of Science ®Google Scholar
• S. Chopra and M.R. Rao, The partition problem, Math. Program. 59 (1993), pp. 87–115. doi: 10.1007/BF01581239
   Web of Science ®Google Scholar
• S. Chopra and M.R. Rao, Facets of the k-partition problem, Discrete Appl. Math. 61 (1995), pp. 27–48. doi: 10.1016/0166-218X(93)E0175-X
   Web of Science ®Google Scholar
• CPLEX, User's Manual for CPLEX, 12th ed., IBM Corporation, 2013.
   Google Scholar
• O. Daxhelet and Y. Smeers, The EU regulation on cross-border trade of electricity: A two-stage equilibrium model, Eur. J. Oper. Res. 181 (2007), pp. 1396–1412. doi: 10.1016/j.ejor.2005.12.040
   Web of Science ®Google Scholar
• S. Dempe, V. Kalashnikov, G.A. Pérez-Valdés, and N. Kalashnykova, Bilevel programming problems, in Energy Systems, Springer, Berlin, 2015.
   Google Scholar
• X. Deng, Complexity issues in Bilevel linear programming, in Multilevel Optimization: Algorithms and Applications, A. Migdalas, P.M. Pardalos, and P. Värbrand, eds., Springer US, 1998, pp. 149–164.
   Google Scholar
• M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics Vol. 15, Springer, Berlin, 1997.
   Google Scholar
• B. Dilkina and C.P. Gomes, Solving connected subgraph problems in wildlife conservation, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14–18, 2010. Proceedings, Springer Berlin Heidelberg, Berlin, 2010, pp. 102–116.
   Google Scholar
• E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), pp. 201–213. doi: 10.1007/s101070100263
   Web of Science ®Google Scholar
• J. Egerer, J. Weibezahn, and H. Hermann, Two price zones for the german electricity market - market implications and distributional effects, Energ. Econ. 59 (2016), pp. 365–381. doi: 10.1016/j.eneco.2016.08.002
   Web of Science ®Google Scholar
• ENTSO-E, All TSOs' draft proposal for Capacity Calculation Regions (CCRs) (2015), Available at https://consultations.entsoe.eu/system-operations/capacity-calculation-regions/consult_view.
   Google Scholar
• P. Festa, P.M. Pardalos, M.G. Resende, and C.C. Ribeiro, Randomized heuristics for the max-cut problem, Optim. Methods Softw. 17 (2002), pp. 1033–1058. Available at http://dx.doi.org/10.1080/1055678021000090033.
   Web of Science ®Google Scholar
• J. Fortuny-Amat and B. McCarl, A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc. 32 (1981), pp. 783–792. doi: 10.1057/jors.1981.156
   Web of Science ®Google Scholar
• A. Frieze and M. Jerrum, Improved approximation algorithms for max k-cut and max bisection, Algorithmica 18 (1997), pp. 67–81. doi: 10.1007/BF02523688
   Web of Science ®Google Scholar
• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979.
   Google Scholar
• A.M. Geoffrion, Generalized Benders decomposition, J. Optim. Theory Appl. 10 (1972), pp. 237–260. doi: 10.1007/BF00934810
   Google Scholar
• A. Ghoniem and H.D. Sherali, Defeating symmetry in combinatorial optimization via objective perturbations and hierarchical constraints, IIE T. 43 (2011), pp. 575–588. doi: 10.1080/0740817X.2010.541899
   Web of Science ®Google Scholar
• M.X. Goemans and D.P. Williamson, New 34-approximation algorithms for the maximum satisfiability problem, SIAM J. Discrete Math. 7 (1994), pp. 656–666. doi: 10.1137/S0895480192243516
   Google Scholar
• V. Grimm, A. Martin, M. Schmidt, M. Weibelzahl, and G. Zöttl, Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes, Eur. J. Oper. Res. 254 (2016), pp. 493–509. doi: 10.1016/j.ejor.2016.03.044
   Web of Science ®Google Scholar
• V. Grimm, L. Schewe, M. Schmidt, and G. Zöttl, Uniqueness of market equilibrium on a network: A peak-load pricing approach, Tech. Rep., 2015, Available at http://www.optimization-online.org/DB_HTML/2015/08/5072.html.
   Google Scholar
• V. Grimm, G. Zöttl, B. Rückel, and C. Sölch, Regionale preiskomponenten im strommarkt. gutachten im auftrag der monopolkommission in vorbereitung des 71. sondergutachtens energie2015 der monopolkommission, (2015), Available at http://www.wirtschaftstheorie.wiso.uni-erlangen.de/wp-content/uploads/2016/02/gutachten_regionale-preiskomponenten07.10.15.pdf.
   Google Scholar
• Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, Version 6.5 (2015).
   Google Scholar
• P. Hansen and N. Mladenovic, An introduction to variable neighborhood search, in Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voß, S. Martello, I.H. Osman, and C. Roucairol, eds., Springer US, 1999, pp. 433–458, Available at http://dx.doi.org/10.1007/978-1-4615-5775-3_30.
   Google Scholar
• P. Holmberg and E. Lazarczyk, Congestion Management in Electricity Networks: Nodal, Zonal and Discriminatory Pricing, Research Institute of Industrial Economics (IFN), 2012. Available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2055655
   Google Scholar
• M. Jenabi, S.M. Fatemi Ghomi, and Y. Smeers, Bi-level game approaches for coordination of generation and transmission expansion planning within a market environment, IEEE T. Power Syst. 28 (2013), pp. 2639–2650. doi: 10.1109/TPWRS.2012.2236110
   Web of Science ®Google Scholar
• V. Kaibel, M. Peinhardt, and M.E. Pfetsch, Orbitopal fixing, in Integer Programming and Combinatorial Optimization, M. Fischetti and D. Williamson, eds., Springer, Berlin, 2007, pp. 74–88.
   Google Scholar
• V. Kaibel and M.E. Pfetsch, Packing and partitioning orbitopes, Math. Program. 114 (2008), pp. 1–36. doi: 10.1007/s10107-006-0081-5
   Web of Science ®Google Scholar
• T. Kleinert, A decomposition approach for a multilevel graph partitioning model of the german electricity market, Master's thesis. FAU Erlangen–Nürnberg, 2016.
   Google Scholar
• H.F. Lee and D.R. Dooly, Decomposition algorithms for the maximum-weight connected graph problem, Nav. Res. Log. (NRL) 45 (1998), pp. 817–837. Available at http://dx.doi.org/10.1002/(SICI)1520-6750(199812)45:8%3C817::AID-NAV4%3E3.0.CO;2-1.
   Web of Science ®Google Scholar
• F. Liers, M. Jünger, G. Reinelt, and G. Rinaldi, Computing exact ground states of hard using spin glass problems by Branch-and-Cut, in New Optimization Algorithms in Physics, Wiley, 2005, pp. 47–69.
   Google Scholar
• A. Lisser and F. Rendl, Graph partitioning using linear and semidefinite programming, Math. Program. 95 (2003), pp. 91–101. doi: 10.1007/s10107-002-0342-x
   Web of Science ®Google Scholar
• F. Margot, Pruning by isomorphism in branch-and-cut, Math. Program. 94 (2002), pp. 71–90. doi: 10.1007/s10107-002-0358-2
   Web of Science ®Google Scholar
• F. Margot, Exploiting orbits in symmetric ilp, Math. Program. 98 (2003), pp. 3–21. doi: 10.1007/s10107-003-0394-6
   Web of Science ®Google Scholar
• F. Margot, Symmetry in integer linear programming, in 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, eds., Springer Berlin Heidelberg, 2010, pp. 647–686.
   Google Scholar
• J. Mitchell, Branch-and-cut for the k-way equipartition problem, 2001.
   Google Scholar
• I. Méndez-Díaz and P. Zabala, A polyhedral approach for graph coloring, Electron. Notes Discret. Math. 7 (2001), pp. 178–181. doi: 10.1016/S1571-0653(04)00254-9
   Google Scholar
• I. Méndez-Díaz and P. Zabala, A branch-and-cut algorithm for graph coloring, Discrete Appl. Math. 154 (2006), pp. 826–847. doi: 10.1016/j.dam.2005.05.022
   Web of Science ®Google Scholar
• J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio, Orbital branching, in Integer Programming and Combinatorial Optimization, Springer, 2007, pp. 104–118.
   Google Scholar
• M.E. Pfetsch and T. Rehn, A computational comparison of symmetry handling methods for mixed integer programs, Optimization Online (2015), Available at http://www.optimization-online.org/DB_HTML/2015/11/5209.html, preprint.
   Google Scholar
• Regionales Rechenzentrum Erlangen, Woodcrest cluster, Available at https://www.rrze.fau.de/dienste/arbeiten-rechnen/hpc/systeme/woodcrest-cluster.shtml.
   Google Scholar
• F. Rendl, G. Rinaldi, and A. Wiegele, Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program. 121 (2008), p. 307. doi: 10.1007/s10107-008-0235-8
   Web of Science ®Google Scholar
• N.V. Sahinidis and I.E. Grossmann, Convergence properties of generalized Benders decomposition, Comput. Chem. Eng. 15 (1991), pp. 481–491. doi: 10.1016/0098-1354(91)85027-R
   Web of Science ®Google Scholar
• H.D. Sherali and J.C. Smith, Improving discrete model representations via symmetry considerations, Manag. Sci. 47 (2001), pp. 1396–1407. doi: 10.1287/mnsc.47.10.1396.10265
   Web of Science ®Google Scholar
• S. Stoft, Transmission pricing zones: simple or complex?, Electricity J. 10 (1997), pp. 24–31. doi: 10.1016/S1040-6190(97)80294-1
   Google Scholar
• The European Commission, Commission regulation (EU) 2015/1222 of 24 july 2015 establishing a guideline on capacity allocation and congestion management (2015), Available at http://eur-lex.europa.eu/legal-content/EN/TXT/PDF/?uri=CELEX:32015R1222&from=EN.
   Google Scholar
• K. Trepper, M. Bucksteeg, and C. Weber, Market splitting in germany—new evidence from a three-stage numerical model of europe, Energy Policy 87 (2015), pp. 199–215. doi: 10.1016/j.enpol.2015.08.016
   Web of Science ®Google Scholar
• V.V. Vazirani, Approximation Algorithms, Springer, Berlin, 2001.
   Google Scholar
• L. Vicente, G. Savard, and J. Júdice, Descent approaches for quadratic bilevel programming, J. Optim. Theory Appl. 81 (1994), pp. 379–399. doi: 10.1007/BF02191670
   Web of Science ®Google Scholar
• J.J. Ye and D.L. Zhu, Optimality conditions for bilevel programming problems, Optimization 33 (1995), pp. 9–27. doi: 10.1080/02331939508844060
   Google Scholar