Optimization Online


A Computationally Efficient Algorithm for Computing Convex Hull Prices

Bernard Knueven (Bernard.Knueven***at***nrel.gov)
James Ostrowski (jostrows***at***utk.edu)
Anya Castillo (arcasti***at***sandia.gov)
Jean-Paul Watson (watson61***at***llnl.gov)

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.

Keywords: Convex hull pricing, electricity markets, unit commitment, Benders decomposition, linear programming

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 09/16/2019
Entry Accepted: 09/16/2019
Entry Last Modified: 01/18/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society