Abstract
We address the solution of certain Mathematical Programs with Equilibrium Constraints (MPECs) in power markets using convex optimization. These MPECs constitute a class of complementarity problems relevant to the design and operation of power markets. Specifically, given a non-convex continuous MPEC of the considered type, we iteratively solve a collection of convex optimization problems that approximate the MPEC until a pre-specified tolerance is reached. We use an insightful example to illustrate the proposed solution technique and a case study to analyze its computational performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
We note that the social welfare is the difference between (1) the area under the demand curve and (2) the area under the supply curve. See Fig. 2.
References
Allevi E, Conejo AJ, Oggioni G et al (2018) Evaluating the strategic behavior of cement producers: an equilibrium problem with equilibrium constraints. Eur J Oper Res 264:717–731. https://doi.org/10.1016/J.EJOR.2017.06.043
Baringo L, Conejo AJ (2014) Strategic wind power investment. IEEE Trans Power Syst 29:1250–1260. https://doi.org/10.1109/TPWRS.2013.2292859
Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge
Castro PM (2015) Tightening piecewise McCormick relaxations for bilinear problems. Comput Chem Eng 72:300–311. https://doi.org/10.1016/J.COMPCHEMENG.2014.03.025
Chang HJ (2014) Economics: the user’s guide. Bloomsbury Press, New York
Colson B, Marcotte P, Savard G (2005) Bilevel programming: a survey. 4OR 3:87–107. https://doi.org/10.1007/S10288-005-0071-0
Conejo AJ, Baringo L (2018) Power system operations. Springer, New York
Conejo AJ, Ruiz C (2020) Complementarity, not optimization, is the Language of markets. IEEE Open Access J Power Energy 7:344–353. https://doi.org/10.1109/OAJPE.2020.3029134
Conejo AJ, Carrión M, Morales JM (2010) Decision making under uncertainty in electricity markets. Springer, New York
Dastidar KG (2004) On Stackelberg games in a homogeneous product market. Eur Econ Rev 48:549–562. https://doi.org/10.1016/S0014-2921(03)00035-7
Dempe S (2019) Computing Locally Optimal Solutions of the Bilevel Optimization Problem Using the KKT Approach. In: Lecture notes on Computer Science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) 11548 LNCS, pp 147–157. https://doi.org/10.1007/978-3-030-22629-9_11
Dempe S (2020) Bilevel optimization: theory, algorithms, applications and a bibliography. Optim Appl 161:581–672. https://doi.org/10.1007/978-3-030-52119-6_20
Dempe S, Dutta J (2010) Is bilevel programming a special case of a mathematical program with complementarity constraints? Math Program 1311(131):37–48. https://doi.org/10.1007/S10107-010-0342-1
Dey SS, Gupte A (2015) Analysis of MILP techniques for the pooling problem. Oper Res 63:412–427. https://doi.org/10.1287/opre.2015.1357
Fortuny-Amat J, McCarl B (1981) A representation and economic interpretation of a two-level programming problem. J Oper Res Soc 32:783. https://doi.org/10.2307/2581394
Gabriel SA, Conejo AJ, Fuller JD et al (2013) Complementarity modeling in energy markets. Springer, New York
Garcés LP, Conejo AJ, García-Bertrand R, Romero R (2009) A bilevel approach to transmission expansion planning within a market environment. IEEE Trans Power Syst 24:1513–1522. https://doi.org/10.1109/TPWRS.2009.2021230
Gurobi Optimization, LLC (2021) Gurobi optimizer reference manual. http://www.gurobi.com. Accessed 2022
Hobbs BF, Metzler CB, Pang JS (2000) Strategic gaming analysis for electric power systems: an MPEC approach. IEEE Trans Power Syst 15:638–645. https://doi.org/10.1109/59.867153
Horst R, Pardalos PM, Thoai NV (2000) Introduction to global optimization. Springer, Boston
Jenabi M, Fatemi Ghomi SMT, Smeers Y (2013) Bi-level game approaches for coordination of generation and transmission expansion planning within a market environment. IEEE Trans Power Syst 28:2639–2650. https://doi.org/10.1109/TPWRS.2012.2236110
Kazempour SJ, Conejo AJ, Ruiz C (2011) Strategic generation investment using a complementarity approach. IEEE Trans Power Syst 26:940–948. https://doi.org/10.1109/TPWRS.2010.2069573
Kleinert T, Labbé M, Ljubić I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. EURO J Comput Optim. https://doi.org/10.1016/J.EJCO.2021.100007
Kolodziej S, Castro PM, Grossmann IE (2013) Global optimization of bilinear programs with a multiparametric disaggregation technique. J Glob Optim 57:1039–1063. https://doi.org/10.1007/S10898-012-0022-1/TABLES/6
Le Thi HA, Pham Dinh T (2018) DC programming and DCA: thirty years of developments. Math Program 169:5–68. https://doi.org/10.1007/s10107-018-1235-y
Le Thi HA, Huynh VN, Pham Dinh T (2014) DC programming and DCA for general DC programs. Adv Intell Syst Comput 282:15–35. https://doi.org/10.1007/978-3-319-06569-4_2
Liberti L, Pantelides CC (2006) An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J Glob Optim 362(36):161–189. https://doi.org/10.1007/S10898-006-9005-4
Lipp T, Boyd S (2016) Variations and extension of the convex-concave procedure. Optim Eng 17:263–287. https://doi.org/10.1007/s11081-015-9294-x
Luenberger DG, Ye Y (2008) Linear and nonlinear programming. Springer, New York
Maurovich-Horvat L, Boomsma TK, Siddiqui AS (2015) Transmission and wind investment in a deregulated electricity industry. IEEE Trans Power Syst 30:1633–1643. https://doi.org/10.1109/TPWRS.2014.2367107
Mehanna O, Huang K, Gopalakrishnan B et al (2015) Feasible point pursuit and successive approximation of non-convex QCQPs. IEEE Signal Process Lett 22:804–808. https://doi.org/10.1109/LSP.2014.2370033
Misener R, Thompson JP, Floudas CA (2011) APOGEE: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput Chem Eng 35:876–892. https://doi.org/10.1016/J.COMPCHEMENG.2011.01.026
MOSEK ApS (2021) MOSEK. https://docs.mosek.com/9.2/faq.pdf. Accessed 2022
Motto AL, Arroyo JM, Galiana FD (2005) A mixed-integer LP procedure for the analysis of electric grid security under disruptive threat. IEEE Trans Power Syst 20:1357–1365. https://doi.org/10.1109/TPWRS.2005.851942
Pineda S, Morales JM (2019) Solving linear bilevel problems using big-MS: not all that glitters is gold. IEEE Trans Power Syst 34:2469–2471. https://doi.org/10.1109/TPWRS.2019.2892607
Ruiz C, Conejo AJ (2009) Pool strategy of a producer with endogenous formation of locational marginal prices. IEEE Trans Power Syst 24:1855–1866. https://doi.org/10.1109/TPWRS.2009.2030378
Sahinidis NV (1996) BARON: a general purpose global optimization software package. J Glob Optim 82(8):201–205. https://doi.org/10.1007/BF00138693
Shen X, Diamond S, Gu Y, Boyd S (2016) Disciplined convex-concave programming. In: 2016 IEEE 55th conference on decision control CDC 2016, pp 1009–1014. https://doi.org/10.1109/CDC.2016.7798400
Siddiqui S, Gabriel SA (2013) An SOS1-based approach for solving MPECs with a natural gas market application. Netw Spat Econ 13:205–227. https://doi.org/10.1007/s11067-012-9178-y
Sioshansi R, Conejo AJ (2017) Optimization in engineering: models and algorithms. Springer, New York
Smola AJ, Vishwanathan SVN, Hofmann T (2005) Kernel methods for missing variables. In: AISTATS 2005—proceedings of the 10th international workshop on artificial intelligence and statistics, pp 325–332
Sriperumbudur BK, Lanckriet GRG (2009) On the convergence of the concave-convex procedure. Adv Neural Inf Process Syst 22:1759–1767
Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Springer, Boston
Wicaksono DS, Karimi IA (2008) Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J 54:991–1008. https://doi.org/10.1002/AIC.11425
Wogrin S, Centeno E, Barquín J (2011) Generation capacity expansion in liberalized electricity markets: a stochastic MPEC approach. IEEE Trans Power Syst 26:2526–2532. https://doi.org/10.1109/TPWRS.2011.2138728
Wogrin S, Pineda S, Tejada-Arango DA (2020) Applications of bilevel optimization in energy and electricity markets. Springer Optim Appl 161:139–168. https://doi.org/10.1007/978-3-030-52119-6_5
Yuille AL, Rangarajan A (2003) The concave-convex procedure. Neural Comput 15:915–936. https://doi.org/10.1162/08997660360581958
Zare MH, Borrero JS, Zeng B, Prokopyev OA (2019) A note on linearized reformulations for a class of bilevel linear integer problems. Ann Oper Res 272:99–117. https://doi.org/10.1007/S10479-017-2694-X/TABLES/13
Zimmerman RD, Murillo-Sanchez CE, Thomas RJ (2011) MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education. IEEE Trans Power Syst 26:12–19. https://doi.org/10.1109/TPWRS.2010.2051168
Zugno M, Morales JM, Pinson P, Madsen H (2013) Pool strategy of a price-maker wind power producer. IEEE Trans Power Syst 28:3440–3450. https://doi.org/10.1109/TPWRS.2013.2252633
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Constante-Flores, G., Conejo, A.J. & Constante-Flores, S. Solving certain complementarity problems in power markets via convex programming. TOP 30, 465–491 (2022). https://doi.org/10.1007/s11750-022-00627-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-022-00627-3