Correction

This article refers to:

Polynomial time algorithms and extended formulations for unit commitment problems

Article title: Polynomial time algorithms and extended formulations for unit commitment problems

Authors: Guan, Y., Pan, K., & Zhou, K.

Journal: IISE Transactions

Bibliometrics: Volume 50, Number 8, pages 735 - 751

DOI: http://dx.doi.org/10.1080/24725854.2017.1397303

In this notice, we correct imprecise statements in the article above [2]. In Proposition 1, we claimed that formulation (9) produces optimal solutions that are binary with respect to α, β, γ and θ for general convex function $w_{tk}^s(q_{tk}^s,{\beta }_{tk}).$ This statement is not precise. Proposition 1 holds for piecewise linear convex functions instead of general convex functions. This can be slightly revised to be a correct conclusion. In fact, constraint (8n) should be kept in the formulation when formulation (8) was reformulated to the formulation (9) by maintaining $w_{tk}^s$ as a decision variable, and thereafter the conclusion in Proposition 1 holds under piecewise linear convex functions. To that end, we make the following corrections:

1. On Page 736 right column: Replace “(ii) …with both general convex and piecewise linear cost functions” with “(ii) …with piecewise linear cost functions.”

2. On Pages 738: Replace “2.2. An extended …with general convex cost function” with “2.2. An extended …with piecewise linear convex cost function.”

3. On Pages 739 and 740 in (8c), (8d), and (9c): Replace “$k=t+L-1$” with “$k=\min \{t+L-1,T\}.$”

4. On Page 740 left column: Delete the paragraph “Note here that …function as $w_{tk}^s(q_{tk}^s,{\beta }_{tk})$”; replace “$w_{tk}^s(q_{tk}^s,{\beta }_{tk})$” with “$w_{tk}^s$” in expression (9a).

5. On Page 740 right column: combine expressions (8n) and (9k) as the new (9k); replace “we assume that” with “since”; replace “with the same set of Constraints (9b)-(9k) but with” with “with the same set of Constraints (9b)-(9k) without the term included in (8n) but with.”

6. On Page 741 right column: In Proposition 1, replace “The” with “There exists an” and delete “is”; replace the entire proof of Proposition 1 with “The conclusion directly follows from Theorem 1 and linear objective function (9a).”

7. On Page 742 left column: Replace “single-UC problem with a general convex cost function …and add” with “single-UC problem by adding.”

8. On Page 742 Theorem 2: Replace “general convex” with “general piecewise linear convex”; replace the objective function “${\sum }_{t=1}^T(S{U}_t+f_t(x_t,y_t))+{\sum }_{t=L}^{T-1}S{D}_t$“with “(9a)”; delete “(1i)-(1k)”; delete the proof section.

9. On Page 742 right column: In Remark 1, replace “but also provides an … due to Theorem 2” with “but also provides an optimal objective converging to that of the deterministic single-UC problem (1) when $f(·)$ is a general convex function due to the compactness of the feasible region and bounded objective value for the single-UC problem and Theorem 2.”

10. On Page 746, replace “$f_t(x_t,y_t)$” with “${\phi }_t$” and “(20b)-(20e)” with “(16), (20b)-(20e)” in Theorem 3.

11. On Page 749, replace “$f_m(x_m,y_m)$” with “${\phi }_m$” and “(29b)-(29e)” with “(26), (29b)-(29e)” in Theorem 4.

The updated integral formulations with the precise statements have been available at https://arxiv.org/abs/1906.07862 (i.e., formulation (2) in Section II and corresponding proof in Section III).

We can observe that our extended formulation not only describes an integral polytope with respect to variables $(y,u,\alpha ,\beta ,\gamma ,\theta )$ due to Theorem 1, but also provides an optimal objective converging to that of the deterministic single-UC problem (1) when $f(·)$ is a general convex function, as the number of line segments increases, due to the compactness of the feasible region and bounded objective value for the single-UC problem. Furthermore, since $f(·)$ is a quadratic function in general, an alternative way to obtain an optimal solution that is binary with respect to variables $(y,u,\alpha ,\beta ,\gamma ,\theta )$ under the quadratic function $f(·)$ is to utilize the convex envelope of $f_t(x_t,y_t)$ as described in [3] (Theorem 3) and the integral polytope proved in our Theorem 1, because Theorem 1 provides an explicit description of the $\mathit{conv}({\mathcal{X}}_g)$ defined in [3]. Thus, following [3], the convex envelope of our original formulation (9) in [2] when $w_{tk}^s$ is a quadratic function (e.g., $w_{tk}^s(q_{tk}^s,{\beta }_{tk})=a_{tk}^s{(q_{tk}^s)}^2+b_{tk}^s{q}_{tk}^s+c_{tk}^s{\beta }_{tk}$) can be described as $$\begin{array}{c}\min {\sum }_{t=1}^{T}SU(s_0+t-1){\alpha }_t+{\sum }_{t=1}^T{\sum }_{k=t+L-1}^{T-1}SD(k-t+1){\beta }_{tk}+\\ {\sum }_{t=L}^{T-\ell -1}{\sum }_{k=t+\ell +1}^{T}SU(k-t-1){\gamma }_{tk}+{\sum }_{tk\in \mathcal{T}\mathcal{K}}{\sum }_{s=t}^k{w}_{tk}^s\\ \mathrm{s}.\mathrm{t}.(9\mathrm{b}) - (9\mathrm{k}),\\ w_{tk}^s=\{\begin{array}{cc}{a}_{tk}^s{(q_{tk}^s)}^2/{\beta }_{tk}+b_{tk}^s{q}_{tk}^s+c_{tk}^s{\beta }_{tk},\hfill & {\beta }_{tk}>0,\hfill \\ 0,\hfill & {\beta }_{tk}=0.\hfill \end{array}\end{array}$$

An independent work compared with [3] is available in [1]. Both of them investigate extended formulations of the UC problem from the perspective of nonlinear programming, while our work in [2] focuses on the extended formulations with piecewise linear convex objective functions in the form of linear program. Finally, the authors thank Yanan Yu, Tiziano Bacci, Antonio Frangioni, and Claudio Gentile for their sincere suggestions.