A Variable Reduction Method for Large-Scale Security Constrained Unit Commitment

Xuan Li, Qiaozhu Zhai, Jingxuan Zhou, Xiaohong GuanarXiv 2018 · DOI · arXiv

Abstract

Efficient methods for large-scale security constrained unit commitment (SCUC) problems have long been an important research topic and a challenge especially in market clearing computation. For large-scale SCUC, the Lagrangian relaxation methods (LR) and the mixed integer programming methods (MIP) are most widely adopted. However, LR usually suffers from slow convergence; and the computational burden of MIP is heavy when the binary variable number is large. In this paper, a variable reduction method is proposed: First, the time-coupled constraints in the original SCUC problem are relaxed and many single-period SCUC problems (s-UC) are obtained. Second, LR is used to solve the s-UCs. Different from traditional LR with iterative subgradient method, it is found that the optimal multipliers and the approximate UC solutions of s-UCs can be obtained by solving linear programs. Third, a criterion for choosing and fixing the UC variables in the SCUC problem is established, hence the number of binary variables is reduced. Last, the SCUC with reduced binary variables is solved by MIP solver to obtain the final UC solution. The proposed method is tested on the IEEE 118-bus system and a 6468-bus system. The results show the method is very efficient and effective.

Introduction

The Security Constrained Unit Commitment (SCUC) problem is the fundamental "brain" of modern power grid operations. It determines the optimal schedule for generating units—deciding which should be online (Unit Commitment) and their specific power outputs (Economic Dispatch)—to meet demand at minimum cost while maintaining grid stability under potential contingencies (N-1 constraints).

As power systems expand to include thousands of generators and tens of thousands of transmission lines, SCUC becomes a Mixed-Integer Programming (MIP) challenge of immense scale. Every generator at every hour represents a binary decision, leading to a combinatorial explosion that standard solvers often cannot resolve within the strict 3-4 hour windows required for day-ahead energy markets. This research addresses this bottleneck by introducing a novel variable reduction strategy.

Methodology: The Variable Reduction Framework

The proposed method aims to prune the search space of the MIP solver by "fixing" certain binary variables that are highly likely to remain constant in the optimal solution. The framework follows a four-step process:

  1. Decomposition (s-UC): The complex multi-period problem is decomposed into independent single-period snapshots by relaxing time-coupled constraints, such as ramping limits and minimum up/down times.
  2. Linear Programming Shortcut (d-UC-LP): Rather than using slow, iterative Lagrangian Relaxation (LR) to solve these snapshots, the authors transform the dual of the single-period problem into a simple Linear Program (LP). This allows for the nearly instantaneous calculation of optimal multipliers and approximate unit statuses.
  3. Variable Selection Criterion: A mathematical distance metric is established to measure the "certainty" of a unit's status. If a unit's status in the simplified LP is far from the switching threshold, it is considered highly certain.
  4. Reduced MIP Solving: Based on a user-defined "Pre-Determined Ratio" (PDR), the most certain binary variables are fixed to their approximate values. The remaining uncertain variables are then solved using a standard MIP solver on the original, full-scale problem.
Flowchart of the proposed variable reduction method for SCUC.

Experimental Evaluation

The method was validated using two benchmark systems: the IEEE 118-bus system (54 units) and a large-scale 6468-bus system (399 units, 9,000 transmission lines). The large-scale system represents a significant computational challenge, with over 432,000 transmission and security constraints.

Results and Discussion

The variable reduction method demonstrated massive efficiency gains with negligible impacts on solution quality. For the 118-bus system, fixing 70% of the variables reduced solver time by 94% (from 1,987 seconds to 121 seconds) with a cost increase of only 0.15%. In the 6468-bus system, computation time dropped from 4,255 seconds to 1,254 seconds, while the total generation cost remained identical to the full-scale solution.

Reduction in problem complexity (rows, columns, nonzeros) as the Pre-Determined Ratio (PDR) increases for the large-scale system.

As shown in the complexity analysis, increasing the PDR significantly reduces the number of rows, columns, and non-zero elements the MIP solver must process. This reduction prunes the "branch-and-cut" tree, leading to the observed exponential speedups. The key insight is that while time-coupled constraints are vital for feasibility, they rarely change the fundamental status of most units, allowing the single-period snapshots to provide a highly accurate starting guess.

Conclusion

By bypassing the iterative subgradient methods of traditional Lagrangian Relaxation and leveraging a one-shot LP formulation, this variable reduction method offers a practical path for solving large-scale SCUC problems. While setting the PDR too high can occasionally lead to infeasibility regarding ramp rates, the method allows for an adaptive approach where the ratio can be lowered if necessary. Future work may involve combining this technique with warm-start methods or applying it to stochastic problems involving renewable energy uncertainty.

Summary updated

Abstract

Efficient methods for large-scale security constrained unit commitment (SCUC) problems have long been an important research topic and a challenge especially in market clearing computation. For large-scale SCUC, the Lagrangian relaxation methods (LR) and the mixed integer programming methods (MIP) are most widely adopted. However, LR usually suffers from slow convergence; and the computational burden of MIP is heavy when the binary variable number is large. In this paper, a variable reduction method is proposed: First, the time-coupled constraints in the original SCUC problem are relaxed and many single-period SCUC problems (s-UC) are obtained. Second, LR is used to solve the s-UCs. Different from traditional LR with iterative subgradient method, it is found that the optimal multipliers and the approximate UC solutions of s-UCs can be obtained by solving linear programs. Third, a criterion for choosing and fixing the UC variables in the SCUC problem is established, hence the number of binary variables is reduced. Last, the SCUC with reduced binary variables is solved by MIP solver to obtain the final UC solution. The proposed method is tested on the IEEE 118-bus system and a 6484-bus system. The results show the method is very efficient and effective.
BibTeX
@misc{li2018variable,
  author = {Xuan Li and Qiaozhu Zhai and Jingxuan Zhou and Xiaohong Guan},
  title = {{A Variable Reduction Method for Large-Scale Security Constrained Unit Commitment}},
  year = {2018},
  eprint = {1810.09096},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.09096},
}
Figure