Optimization Online


A Computationally Efficient Algorithm for Computing Convex Hull Prices

Bernard Knueven(bknueve***at***sandia.gov)
James Ostrowski(jostrows***at***utk.edu)
Anya Castillo(arcasti***at***sandia.gov)
Jean-Paul Watson(jwatson***at***sandia.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 execute side payments when a participant’s cost is not covered through energy sale settlements from locational marginal pricing schemes, or when a participant incurs lost opportunity costs to follow the dispatch signal. Convex hull pricing minimizes these and other types of side payments while providing uniform (i.e., locationally and temporally consistent) prices. However, computing convex hull prices involves solving either a large-scale linear program – which in turn requires explicit descriptions of market participants’ convex hulls – or the Lagrangian dual of the corresponding non-convex scheduling problem. Here, we propose a computationally feasible and industrially scalable Benders decomposition approach to computing convex hull prices at least an order of magnitude faster than the current state-of-the-art while leveraging recent advances in convex hull formulations for thermal generating units.

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

Category 1: Applications -- OR and Management Sciences

Citation: SAND2019-10896 J; Sandia National Laboratories, Albuquerque, NM; September 2019.

Download: [PDF]

Entry Submitted: 09/16/2019
Entry Accepted: 09/16/2019
Entry Last Modified: 09/16/2019

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