Novel Quality Measure and Efficient Resolution of Convex Hull Pricing for Unit Commitment

Consider a UC problem with $I$ units indexed by $i$ and $T$ hours indexed by $t$.

1. 1.

   Objective Function: The goal is to minimize the total cost as:

   $\displaystyle\min_{\left\{x_{i},u_{i},p_{i},r_{i}\right\}}{\left\{\sum_{i=1}^{I}{z_{i}\left(x_{i},u_{i},p_{i},r_{i}\right)}\right\}},$

   (1)

   where $z_{i}\left(x_{i},u_{i},p_{i},r_{i}\right)=\displaystyle\sum_{t=1}^{T}\left(c_{i}^{E}\left(p_{i,t}\right)+c_{i}^{S}\cdot u_{i,t}+c_{i}^{N}\cdot x_{i,t}\right)$ represents the total cost of unit $i$, including energy costs, start-up costs, and no-load costs. Decision variables at time $t$ are: 1. binary commitment $x_{i,t}$ and start-up $u_{i,t}$; and 2. continuous dispatch $p_{i,t}$ .

2. 2.

   System-Wide Constraints

   System Demand: The total power generation equals the demand at each time $t$:

   $\displaystyle\sum_{i=1}^{I}p_{i,t}=D_{t},t=1,\ldots,T,$

   (2)

   where $p_{i,t}$ are generation levels and $D_{t}$ is the demand at time $t$.

3. 3.

   Unit-Level Constraints

   1. (a)

      Generation Capacity Constraints: The generation capacity for online units $(x_{i,t}=1)$ is restricted by a lower limit and an upper limit, denoted by $P_{i}^{min}$ and $P_{i}^{max}$, respectively. Meanwhile, when a unit is offline, represented by the corresponding commitment status $x_{i,t}=0$, its generation level is zero. The mathematical constraints capturing these relationships are provided below:

      $\displaystyle x_{i,t}\cdot P_{i}^{min}\leq p_{i,t}\leq x_{i,t}\cdot P_{i}^{max},$

      (3)

   2. (b)

      Start-Up Constraints: Start-ups are captured by using binary variables $u_{i,t}$ as:

      $\displaystyle x_{i,t}-x_{i,t-1}\leq u_{i,t}.$

      (4)

      In the above relationship, a start-up cost is incurred when $u_{i,t}=1,$ which is only possible when $x_{i,t}=1$ and $x_{i,t-1}=0.$

   3. (c)

      Minimum Up- and Down-Time Constraints: Unit $i$ stays online (offline) for its minimum up- (down-) time $l_{i}(L_{i})$:

      $\displaystyle\sum_{j=t-L_{i}+1}^{t}u_{i,j}\leq x_{i,t},\ \sum_{j=t-l_{i}+1}^{t}u_{i,j}\leq 1-x_{i,t-l_{i}}.$

      (5)

   4. (d)

      Ramp-Rate Constraints: The change of generation levels between two consecutive hours cannot exceed its ramp-rate requirements:

      $\displaystyle p_{i,t}-p_{i,t-1}\leq R_{i}\cdot x_{i,t-1}+V_{i}\cdot\left(1-x_{i,t-1}\right),$

      (6)

      $\displaystyle p_{i,t-1}-p_{i,t}\leq R_{i}\cdot x_{i,t}+V_{i}\cdot\left(1-x_{i,t}\right),$

      (7)

      where $R_{i}$ are ramp-up/down and $V_{i}$ is the start-up/shut-down ramp rates.

The above UC problem formulation does not consider transmission constraints. However, transmission constraints are often included in practical situations. In such cases, the following constraints are added to the formulation instead of the demand constraint in (2):

1. 1.

   DC Power Flow Constraints: The power flow on each transmission line $l$ at time $t$ is given by:

   $\displaystyle f_{l,t}=\frac{\theta_{s\left(l\right),t}-\theta_{r\left(l\right),t}}{X_{l}},l=1,\ldots,L,t=1,\ldots,T.$

   (8)

   Here $\theta_{s\left(l\right),t}$ and $\theta_{r\left(l\right),t}$ are phase angles at sending and received buses of line $l$, and $X_{l}$ is line $l$ impedance.

2. 2.

   Nodal Flow Balance Constraints: Nodal flow balance is maintained at each node $n$=1,$\ldots,N$ by the following equation:

   $\displaystyle\sum_{l:r\left(l\right)=n}f_{l,t}+p_{n,t}=\sum_{l:s\left(l\right)=n}f_{l,t}+D_{n,t},\ t=1,\ldots,T.$

   (9)

3. 3.

   Transmission Capacity Constraints: The power flow on each transmission line $l$ is limited by its minimum and maximum capacity:

   $\displaystyle f_{l}^{min}\leq f_{l,t}\leq f_{l}^{max},l=1,\ldots,L,t=1,\ldots,T.$

   (10)

For simplicity, the explanation will rest upon the formulation with system demand constraints; a formulation with transmission constraint follows analogously. The dual problem to the UC problem is defined as [10]:

The methodology to be presented will be based on the above. Extension for the formulation with transmission follows the same logic with the exception that nodal flow balance constants (9) are relaxed rather than system demand constraints (2), in which case the multipliers $\lambda$ will be a matrix.

In this subsection, our recent Surrogate Lagrangian Relaxation (SLR) Method will be briefly introduced. Within the method, multipliers are updated based on “surrogate” subgradients $g\left(\tilde{p}^{k}\right)$ (which are levels of constraint violations of relaxed constraints), and stepsizes $s_{SLR}^{k}$ as:

where,

Here, “tilde” ($\texttildelow$) indicates that optimization of the relaxed problem is subject to the following “surrogate optimality condition” [9, p. 178, eq. (12)]: $L\left(\lambda^{k},\ \tilde{x}^{k},\ \tilde{u}^{k},\ \tilde{p}^{k}\right)<$ $L\left(\lambda^{k},\ \tilde{x}^{k-1},\ \tilde{u}^{k-1},\ \tilde{p}^{k-1}\right)$, rather than to full minimization the Lagrangian function in (12), with $L\left(\lambda^{k},\ \tilde{x}^{k},\ \tilde{u}^{k},\ \tilde{p}^{k}\right)$ being a “surrogate dual value” (a value that the Lagrangian function (13) attains at solutions $\tilde{x}^{k},\ \tilde{u}^{k},\ \tilde{p}^{k}$). The primary advantages of the SLR method lie in the fact that it does not require solving all sub-problems simultaneously and only needs to satisfy the surrogate optimality condition mentioned earlier. Both of these factors contribute to a significant reduction in computational effort. Moreover, surrogate directions do not change drastically from one iteration to the next, and zigzagging difficulties are thus alleviated. Thereby also contributing to the overall significant reduction of the computational effort.

This subsection is on a novel way to obtain the upper bound $\bar{q}$ to the optimal dual value $q\left(\lambda^{\ast}\right)$, approaching $q\left(\lambda^{\ast}\right)$ from above. Together with dual values $q\left(\lambda^{k}\right)$ (which are a lower bound), the novel CH-price quality measure will be obtained as a relative difference between $\bar{q}$ and $q\left(\lambda^{k}\right)$.

As proved within the “Surrogate” Subgradient Method (SSM) [11, pp. 704-706], if the following condition on stepsizes holds

then multipliers approach $\lambda^{*}$ at every iteration:

However, the optimal dual value $q^{*}$ required to set stepsizes is generally not known for any given problem. Therefore, when stepsizes are set by using any other rule without using $q^{*}$, then multipliers may not approach $\lambda^{*}$ (or any other point) at every iteration. This “non-approaching” property will be exploited to derive the novel quality measure. Specifically, if one can detect that multipliers do not approach $\lambda^{*}$, then this is only because stepsizes are “too large,” that is, stepsizes violate (16). This result is summarized in the following Lemma.

Lemma: If there exists $\kappa$ so that $\lambda^{\ast}$ move away from $\lambda^{\ast}$, i.e.,

then

Proof: Denote (16) as assertion A and (17) as B. According to [11, pp. 704-706], the following predicate holds true: $\forall k:\ A\rightarrow B$. In the proof, the following relation will be helpful:

Negation of the predicate $\forall k:\ A\rightarrow B$ leads to $\exists k:\ \lnot(A\rightarrow B)$, which simplifies to $\exists k:\ \lnot A\vee B$, which is equivalent to $\exists k:\ B\vee\left(\lnot A\right)$ by the commutative property of disjunctions. By (20), the latter predicate is equivalent to $\exists k:(\lnot B)\rightarrow\left(\lnot A\right)$. \qed

According to (18), there exists an overestimate of the optimal dual value $\bar{q}>q^{\ast}$ such that

From (21), the overestimate can be expressed as:

However, the difficulty is that (22) was determined based on the inequality (18) which involves the unknown $\lambda^{\ast}$, and the upper bound (22) cannot be computed. To resolve this difficulty, the following assumption is used.

The above assumption is realistic. Otherwise, multipliers would always strictly approach $\lambda^{\ast}$ and converge to $\lambda^{\ast}$. The latter is by the design of the SLR method [9], yet, the former can only be guaranteed if the SSM stepsize (16) is used.

The problem (23) is set up starting from values $\lambda^{k}$ and $\lambda^{k+1}$ and one inequality. After $\lambda^{k+2}$ is obtained, the second inequality is added, and so on until a certain $k+n-1$ ($n$ is not known beforehand) iteration is reached whereby (23) is infeasible.

Since at one of the iterations $k,\dots,k+n-1$, equality (19) holds, the sought-for upper bound is then obtained as:

Subsequently, values of $k$ and $n$ are reset as $k\rightarrow k+n,\ n\rightarrow 1$, and the procedure repeats.

Finally, the quality measure of the CH prices is defined as $\frac{{\bar{q}}^{k}-q^{k}}{{\bar{q}}^{k}}$, where ${\bar{q}}^{k}$ is the best (lowest) upper bound, and $q^{k}$ is the best (highest) dual value obtained up to iteration $k$. This measure can be used as a stopping criterion.

Unlike feasible costs, the novel upper bound approaches the optimal dual value from above since the upper bound (24) depends on the stepsizes approaching zero and the Lagrangian function approaching the optimal dual value, as proved in [9]. Another implication of the above is that the fast convergence of SLR leads to fast convergence of the upper bound to the optimal dual value.

Consider a UC problem with two units with the following characteristics:

• 1.

  Unit 1: Pmin = 50 MW, Pmax = 200 MW, initial ramp rate = 150.3 MW/hr and general ramp rate = 200.6 MW/hr, generation cost: 65 $/MW and start-up cost: 0.

• 2.

  Unit 2: Pmin = 50 MW, Pmax = 200 MW, initial ramp rate = 70.35 MW/hr and general ramp rate = 40.7 MW/hr, generation cost: 40 $/MW, start-up cost: $6000.

The results are shown in Figure 2. Our SLR method obtains near-optimal CH prices with a quality of 0.012% in 40 sec. Compared to the duality gap of 10.51%, the novel quality measure of 0.012% is significantly more accurate. The amount of time required to obtain the upper bound is 0.448 sec, which is roughly 1% of the total time (40 sec). The amount of time required to obtain the feasible cost is slightly longer at 0.6 sec.

Consider a 54-unit, 24-hour UC problem based on the IEEE 118-bus system. The results are shown in Figure 3. Compared to the duality gap of 11.13%, the novel quality measure of 0.033% is significantly more accurate. Near-optimal CH prices with a quality of 0.033% are obtained in 25 sec. The amount of time required to obtain the upper bound is 0.617 sec, which is roughly 2.2% of the total time. The amount of time required to obtain the feasible cost is slightly longer at 0.647 sec.

Consider the same problem of Example 2 with transmission capacity constraints. The results obtained by using SLR are shown in Figure 4. Near-optimal CH prices with quality of 0.1% are obtained in 290 sec. Compared to the duality gap of 2.67%, the novel quality measure of 0.1% is more accurate. The amount of time required to obtain the upper bound is 0.7 sec, which is roughly 0.22% of the total time. The amount of time required to obtain the feasible cost is longer at 1.57 sec.

Based on the three examples described above, the following observations can be made:

1. 1.

   The results of Example 4.2 (118-bus without transmission capacity constraints) are comparable to those obtained for a smaller problem of Example 4.1, in terms of CPU time and CH-price quality. The novel quality measure is significantly more accurate than the duality gap.

2. 2.

   The results of Example 4.3 (118-bus with transmission capacity constraints) show the impact of transmission line constraints on solving time and CH-price. However, the novel quality measure is still more accurate than the duality gap.

3. 3.

   Compared to the problem-dependent standard duality gaps, which may be large, the novel quality measures are problem-independent and are more accurate.

Computationally, the standard quality gap requires a feasible solution. When the number of units increases, the time required to obtain a feasible solution is expected to increase. The CPU time required to compute the novel quality measure is not expected to increase for larger-scale problems since the number of decision variables within (23) is independent of the number of units, paving the way for providing a tight measure of CH prices for large-scale problems within a modest CPU time.