A Computationally Efficient Algorithm for Computing Convex Hull Prices

Bernard Knueven, James Ostrowski, Anya Castillo, Jean-Paul Watson

Research output: Contribution to journalArticlepeer-review

1 Scopus Citations

Abstract

Electricity markets worldwide allow participants to bid non-convex production offers. While non-convex offers can more accurately reflect a resource's capabilities, they create challenges for market clearing processes. For example, system operators may be required to execute side payments to participants whose costs are not covered through energy sales as determined via traditional locational marginal pricing schemes. Convex hull pricing minimizes this and other types of side payments while providing uniform (i.e., locationally and temporally consistent) prices. Computing convex hull prices involves solving either a large-scale linear program or the Lagrangian dual of the corresponding non-convex scheduling problem. Further, the former approach requires explicit descriptions of market participants’ convex hulls. While linear programs for computing convex hull prices are large, their structure is naturally decomposable by generators. Here, we propose and empirically analyze a Benders decomposition approach to computing convex hull prices that leverages recent advances in convex hull formulations for thermal generating units. We demonstrate across a large set of test instances that our decomposition approach only requires modest computational effort, obtaining solutions at least an order of magnitude faster than the equivalent large-scale linear programming approach. Overall, we provide a computationally feasible method for computing convex hull prices for industrial scale market clearing problems, enabling the possibility of practical adoption of this advanced pricing mechanism.

Original languageAmerican English
Article number107806
Number of pages13
JournalComputers and Industrial Engineering
Volume163
DOIs
StatePublished - 2022

Bibliographical note

Publisher Copyright:
© 2021 Elsevier Ltd

NREL Publication Number

  • NREL/JA-2C00-77070

Keywords

  • Benders decomposition
  • Convex hull pricing
  • Electricity markets
  • Linear programming
  • Unit commitment

Fingerprint

Dive into the research topics of 'A Computationally Efficient Algorithm for Computing Convex Hull Prices'. Together they form a unique fingerprint.

Cite this