Copositive Duality for Discrete Energy Markets

Optimization problems with discrete decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices. It was shown in Burer (2009) that mixed-binary quadratic programs can be written as completely positive programs, which are convex. We apply this perspective by writing unit commitment in power systems as a completely positive program and then using the dual copositive program and strong duality to design new pricing mechanisms. We show that the mechanisms are revenue-adequate and, under certain conditions, support a market equilibrium. To facilitate implementation, we also employ a cutting plane algorithm for solving copositive programs exactly, which we further speed up via a second-order cone programming approximation. We provide numerical examples to illustrate the potential benefits of the pricing mechanisms and algorithms. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.00906 .