NSF-NSERC: Pricing in Discrete Markets Using Copositive Duality

About This Grant

This award intends to improve infrastructure operations by supporting research on new economic mechanisms for markets with discrete decisions. A prominent example is unit commitment, which schedules when each fuel-burning generator in a power system is on and off. Startup and shutdown account for a significant portion of the cost of generation, and they are binary decisions because a generator can only be on or off. The discreteness of unit commitment undermines standard economic mechanisms. In particular, resulting prices are generally too low, so that system operators must make out-of-market uplift payments to keep generators profitable. In general, discreteness such as this can create negative incentives in markets, leading to inefficient investment and decision-making. Research to be completed in association with this project intends to offer a new approach to designing pricing mechanisms in discrete markets, with the focus on power systems and electric vehicle charging. It will produce new tools and deepen understanding of tradeoffs in discrete markets. The project team has expertise in power systems and transportation, optimization, and market design, and will train graduate students with the multidisciplinary perspectives needed for this project. This project will investigate the use of copositive programming as a tool for designing economic mechanisms for discrete markets. The approach is based on a fundamental result from Burer (2009), which establishes that a mixed-integer linear program can be equivalently represented as a copositive program. Copositive programming is a conic optimization class that is both convex and NP-hard. As such, it does not provide a better way to solve mixed-integer linear programs. However, its convexity does provide a new notion of duality for discrete problems. Therefore, given the copositive representation of a discrete problem like unit commitment, the dual is immediately available in standard form. The dual variables have economic interpretations as shadow prices and can be used to design market mechanisms such as prices and option contracts. Convexity also brings tools like the Karush-Kuhn-Tucker conditions, which are helpful for establishing properties such as efficiency, revenue adequacy, and fairness. This project will explore how to use these and other features of copositivity to better understand and design discrete markets. As copositive programming is computationally hard and of relatively recent interest, it does not yet have mature solution techniques. This project also aims to make copositive programming more practical via the use of machine learning-based, distributed, and online algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.