  Recently increasing penetration of renewable energy generation brings
challenges for power system operators to perform efficient power generation
daily scheduling, due to the intermittent nature of the renewable generation
and discrete decisions of each generation unit. Among all aspects to be
considered, a unit commitment polytope is fundamental and embedded in the
models at different stages of power system planning and operations. In this
paper, we focus on deriving polynomial time algorithms for the unit commitment
problems with general convex cost function and piecewise linear cost function
respectively. We refine an $\mathcal{O}(T^3)$ time, where $ T $ represents the
number of time periods, algorithm for the deterministic single-generator unit
commitment problem with general convex cost function and accordingly develop an
extended formulation in a higher dimensional space that can provide an integral
solution, in which the physical meanings of the decision variables are
described. It means the original problem can be solved as a convex program
instead of a mixed-integer convex program. Furthermore, for the case in which
the cost function is piecewise linear, by exploring the optimality conditions,
we derive more efficient algorithms for both deterministic (i.e.,
$\mathcal{O}(T)$ time) and stochastic (i.e., $\mathcal{O}(N)$ time, where $N$
represents the number of nodes in the stochastic scenario tree)
\rred{single-generator} unit commitment problems. We also develop the
corresponding extended formulations for both deterministic and stochastic
single-generator unit commitment problems that solve the original mixed-integer
linear programs as linear programs. Similarly, physical meanings of the
decision variables are explored to show the insights of the new modeling
approach.
