  In certain electricity markets, because of non-convexities that arise from
their operating characteristics, generators that follow the independent system
operator's (ISO's) decisions may fail to recover their cost through sales of
energy at locational marginal prices. Discriminatory side payments are made by
the ISO to incentivize the compliance of generators. Convex hull pricing is a
uniform pricing scheme that minimizes these side payments. The Lagrangian dual
problem of the unit commitment problem has been used to determine convex hull
prices. However, this approach is computationally expensive. In this paper, we
propose a polynomially-solvable primal formulation for the Lagrangian dual
problem. This formulation explicitly describes for each generating unit the
convex hull of its feasible set and the convex envelope of its cost function.
We cast our formulation as a second-order cone program when the cost functions
are quadratic, and a linear program when the cost functions are piecewise
linear. A 96-period 76-unit transmission-constrained example is solved in less
than fifteen seconds on a personal computer.
