Nonconvex markets


#1

I N T R O D U C T I O N

A nonconvex market refers to the process of obtaining price information from a dispatch problem that contains binary or integer variables.

Projects which embed meshed AC transmission networks normally use simplified power flow analysis (the so-called enhanced “DC” approximation) and linearized quadratic loss functions to help determine the economic dispatch. A linear problem is, of course, much faster to solve than a mixed-integer problem. But another issues arises with nonconvex markets: locational marginal prices (LMP) cannot be obtained by simply inspecting the reduced cost at each node.

Binary variables are typically introduced to aid the characterization of thermal plants, including allowing plants to trip at part load.

From about 2002, literature has been slowly developing about how best to recover sensible prices from MIP dispatch models.

My interest in this area is that I implemented an object-oriented framework (framework seems to be the right term these days) for modeling such systems, with each AC transmission element and bus an object, as well as each power plant and load an object. While the transmission and bus characterizations are linear, the user can include power plants that are mixed-integer in nature.

There may not be much interest in this topic, given that relatively few of the published open energy system models support auctions (by my reckoning: Balmorel, DIETER, EMLab-Generation, EMMA, and NEMO) and fewer still support endogenous bidding.

The application of this work is however more general than indicated, because MIP formulations are used not only for dispatch, but also for lumpy investment and endogenous technological learning (DeCarolis et al 2017).


#2

R E F E R E N C E S
editable wikipost

Bompard, E, T Huang, and W Lu. (2010). “Market power analysis in the oligopoly electricity markets under network constraints”. IET Generation, Transmission and Distribution. 4 (2): 244–256. doi:10.1049/iet-gtd.2009.0018.

DeCarolis, Joseph, Hannah Daly, Paul Dodds, Ilkka Keppo, Francis Li, Will McDowall, Steve Pye, Neil Strachan, Evelina Trutnevyte, Will Usher, Matthew Winning, Sonia Yeh, and Marianne Zeyringer. (15 May 2017). “Formalizing best practice for energy system optimization modelling”. Applied Energy. 194: 184–198. ISSN 0306-2619. doi:10.1016/j.apenergy.2017.03.001.

Delarue, Erik, David Bekaert, Ronnie Belmans, and William D’haeseleer. (2007). “Development of a comprehensive electricity generation simulation model using a mixed integer programming approach”. World Academy of Science, Engineering and Technology. 99–104. ISSN 1307-6892.

Elliott, Matthew. (2012). Inefficiencies in networked markets. Unpublished.

Fernández-López, José M, Álvaro Baíllo, Santiago Cerisola, and Rafael Bellido. (2005). Building optimal offer curves for an electricity spot market: a mixed-integer programming approach. Liege, Belgium, 22-26 August 2005: 15th Power Systems Computation Conference.

Gabriel, Steven A, Antonio J Conejo, J David Fuller, Benjamin F Hobbs, and Carlos Ruiz. (2013). Complementarity modeling in energy markets. New York, USA: Springer. ISBN 978-1-4419-6122-8. doi:10.1007/978-1-4419-6123-5.

Gabriel, Steven A, Antonio J Conejo, Carlos Ruiz, and Sauleh Siddiqui. (May 2013). “Solving discretely constrained, mixed linear complementarity problems with applications in energy”. Computers & Operations Research. 40: 1339–1350. ISSN 0305-0548. doi:10.1016/j.cor.2012.10.017.

Gribik, Paul R, William W Hogan, and Susan L Pope. (31 December 2007). Market-clearing electricity prices and energy uplift. Unpublished.

Guzelsoy, M, and TK Ralphs. (April 2007). Duality for mixed-integer linear programs. Unpublished.

Leuthold, Florian, Hannes Weigt, and Christian von Hirschhausen. (July 2008). ELMOD: a model of the European electricity market — MPRA paper 65660.

Linderoth, JT, and TK Ralphs. (January 2005). Noncommercial software for mixed-integer linear programming. Unpublished.

Makkonen, Simo, and Risto Lahdelma. (16 June 2006). “Non-convex power plant modelling in energy optimisation”. European Journal of Operational Research. 171: 1113–1126. ISSN 0377-2217. doi:10.1016/j.ejor.2005.01.020.

Martin, Alexander, Johannes C Müller, and Sebastian Pokutta. (2 January 2014). “Strict linear prices in non-convex European day-ahead electricity markets”. Optimization Methods and Software. 29: 189–221. ISSN 1055-6788. doi:10.1080/10556788.2013.823544.

Martin, Alexander, Johannes C Müller, and Sebastian Pokutta. (5 May 2014). Linear clearing prices in non-convex European day-ahead electricity markets — TR-2011-02.

Motto, AL, and FD Galiana. (February 2004). “Unit commitment with dual variable constraints”. IEEE Transactions on Power Systems. 19: 330–338. ISSN 0885-8950. doi:10.1109/TPWRS.2003.821443.

Oggioni, Giorgia, and Yves Smeers. (2012). Market failures of market coupling and counter-trading in Europe: an illustrative model based discussion. nil Energy Economics. doi:10.1016/j.eneco.2011.11.018.

O’Neill, Richard P. (July 2007). Equilibrium prices in power exchanges with non-convex bids. Unpublished.

Ruiz, Carlos, Antonio J Conejo, and Steven A Gabriel. (August 2012). “Pricing non-convexities in an electricity pool”. IEEE Transactions on Power Systems. 27: 1334–1342. ISSN 0885-8950. doi:10.1109/TPWRS.2012.2184562.

Sioshansi, Ramteen, Richard O’Neill, and Oren Shmuel S. (1 May 2008). “Economic consequences of alternative solution methods for centralized unit commitment in day-ahead electricity markets”. IEEE Transaction on Power Systems. 23: 344–352. doi:10.1109/TPWRS.2008.919246.

van Vyve, Mathieu. (October 2011). Linear prices for non-convex electricity markets: models and algorithms — Discussion paper 2011/50. Louvain-la-Neuve, Belgium: Center for Operations Research and Econometics (CORE).


#3

As a general comment, prices in non-convex markets cannot be guaranteed to lead to a unique dispatch except in special cases. This is the case for both integer-based and continuous nonconvexities. In general, one must work with payments/lump sums in addition to prices to ensure compliance from participants.

The following citation looks at defining incentive-compatible uplift payments in addition to the prices for producers with binary decision variables. In their model, these uplift payments are assumed to be paid by consumers, representing an equivalent loss in social welfare:

Huppmann, Daniel, and Sauleh Siddiqui (April 2015) An exact solution method for binary equilibrium problems with compensation and the power market uplift problem DIW Discussion Paper 1475.

In short, one looks at what the plant has incentives to do under current prices, and calculates the necessary uplift to be given as a bonus if the plant follows the dispatcher’s signal.

For your simulation, perhaps the agent could report the uplift needed to ensure compliance with the schedule expected by the requested dispatch?


#4

Hi

I would be happy to contribute along the way but from the perspective of algorithms used in a commercial tool (PLEXOS) for now.

This may be valuable for comparative purposes against open tools.


#5

Would there be any difference if the markets were Energy vs. Capacity? I’m studying the “Great Debate” in the RTO/ISO sector and there seems to be a BIG difference between the two. Wasted energy, higher max. prices, etc.

Just curious, or I maybe totally offbase.


#6

Thanks to @TueVJ for referencing to my paper - added here with the link to the open-source GAMS code, if anyone wants to play around…

Daniel Huppmann and Sauleh Siddiqui. “An exact solution method for binary equilibrium problems with compensation and the power market uplift problem”, DIW Discussion Paper 1475, 2015.

GAMS Code for illustrative example and medium-scale dataset on GitHub,
published under a Creative Commons Attribution License


#7

@robbie.morrison Thanks for bringing up this interesting (and challenging) problem. However, in your exposition, I think that you are mixing up terminology of two relevant but distinct issues:

  • correct AC power flow modelling is a non-convex but continuous problem. The difficulty is not so much finding a solution (and associated dual variables a.k.a. prices for that solution) but determining that the identified solution is indeed optimal.

  • on/off decisions of a power plant or lumpy investment decisions require binary or integer variables - in this case, determining dual variables is not generally possible, and there may be situations where no market-clearing prices in the sense of a Walrasian auctioneer exist (i.e., there is no market equilibrium given linear prices).

Cheers,
Daniel


#8

Hi openmoders interested in pricing of non-convex markets!

To follow up on my previous comments, my article with Sauleh Siddiqui on exact reformulations of binary-equilibrium problems and market-clearing prices and uplifts in unit-commitment problems was just accepted in EJOR.

Daniel Huppmann and Sauleh Siddiqui, European Journal of Operation Research (2017). doi:10.1016/j.ejor.2017.09.032

Cheers,
Daniel


Modeling PV-Feed-In