求解安全约束机组组合的定制化混合分支方法

doi:10.19595/j.cnki.1000-6753.tces.250683

摘要
图/表
参考文献
相关文章 (12)

全文: PDF (525 KB)
输出: BibTeX | EndNote (RIS)

摘要

随着电力现货市场交易范围的不断扩大,通用混合整数规划求解器求解大规模安全约束机组组合模型愈发困难。本着破解商用求解器卡脖子难题的初衷,本文提出了一种混合分支方法对开源HiGHS求解器的分支策略进行定制,该方法由变量选择规则及规则切换策略组成,变量选择规则利用机组组合物理模型中0-1变量类型、机组容量、时段顺序和费用等方面特点;规则切换策略则针对分支过程间隙下降瓶颈问题确定了容量混合规则与平均费用规则的切换条件。此外,还根据0-1变量类型对应用强分支的策略进行了定制。IEEE118节点系统、RTE1888节点系统及Polish2383节点系统的仿真结果表明,所提混合分支方法能产生较小搜索树,能够使开源HiGHS求解器求解SCUC问题的速度提升46%~ 62%。所提定制化方法为我国开发自主可控的安全约束机组组合求解器提供了新的思路。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	李佩杰
	葛佳伟
	袁沐琛
	徐胜男

关键词 ：安全约束机组组合, 混合整数线性规划, 求解器, 分支方法, 开源

Abstract：

The Security Constrained Unit Commitment (SCUC) problem plays a critical role in ensuring the fairness and economic efficiency of electricity spot market transactions. In electricity market clearing, SCUC is typically formulated as a Mixed Integer Linear Programming (MILP) model, whose solution efficiency heavily depends on the performance of commercial MILP solvers. With the expanding trading scope of the electricity spot market, it becomes increasingly difficult for generalized mixed integer programming solvers to solve large-scale security constrained unit commitment models. With the original intention of solving the neck problem of commercial solver, this study develops a hybrid branching method by exploiting distinctive features of the SCUC physical mode—including binary variable types, generator capacities, temporal sequencing patterns, and cost structures—to customize the branching strategy of the open?source HiGHS solver. he proposed method consists of variable selection rules and a rule switching strategy.
The variable selection rule integrates two complementary components: the capacity hybrid rule and the average cost rule. The capacity hybrid rule integrates unit capacity into the evaluation value of candidate branching variables as weighting factors while resolving decision conflicts among equally evaluation values variables through temporal precedence. When multiple candidate branching variables have identical evaluation scores, those from earlier time intervals are assigned higher branching priority. This dual mechanism accounts for both the magnitudes of evaluation and the different impacts of the temporal interdependencies across multi-interval decision horizons. The capacity hybrid rule serves as the primary variable selection rule within the hybrid branching method and largely dictates its overall efficiency. Unit costs and temporal characteristics are incorporated into the average cost rule, where variables with maximal evaluation values are selected among minimum-cost candidates. This rule has a high probability of generating nodes that can be pruned, diversifies the search paths of the Branch-and-Cut (B&C) algorithm and provides useful information for it, and as a supplementary component within the hybrid branching method.
The rule switching strategy determines the switching conditions between the capacity hybrid rule and the average cost rule for the bottleneck problem of the gap reduction in the branch process. This enables dynamic adjustment of the branching variable selection logic during the solving process through the strategic alternation of variable selection rules. When stagnation in the optimality gap reduction is detected, the hybrid branching method automatically switches the active variable selection rule to steer the B&C algorithm away from local optima. Furthermore, the hybrid branching method refines the candidate branching variable set by filtering variables according to the physical characteristics implied by binary variable types and customizes the application of strong branching to address reliability issues in the branching evaluation scores of candidate branching variables. Simulation results from the IEEE118 bus, RTE1888 bus, and Polish2383 bus systems demonstrate that using the capacity hybrid rule alone without any rule switching for variable selection improves the speed of the HiGHS solver for SCUC problems by 27% to 49%. When the hybrid branching method dynamically switches variable selection rules, the solving efficiency of HiGHS is further enhanced, achieving an overall speedup of 46% to 62% compared to its original performance. The proposed customized method provides a new idea for the development of an independent and controllable security constrained unit commitment solver in China.

Key words： security constrained unit commitment mixed integer linear programming solver branching method open source

收稿日期: 2025-04-24

PACS:

TM73

通讯作者: 葛佳伟男,1999年生,硕士研究生,研究方向为电力系统最优运行等。E-mail：1367678967@qq.com

作者简介: 李佩杰男,1984年生,博士,副教授,研究方向为电力系统最优运行等。E-mail：lipeijie@gxu.edu.cn

引用本文:

李佩杰, 葛佳伟, 袁沐琛, 徐胜男. 求解安全约束机组组合的定制化混合分支方法[J]. 电工技术学报, 0, (): 1-. Li Peijie, Ge Jiawei, YUAN Muchen, Xu Shengnan. A Customized Hybrid Branching for Solving Security Constrained Unit Commitment Problems. Transactions of China Electrotechnical Society, 0, (): 1-.

链接本文:

https://dgjsxb.ces-transaction.com/CN/10.19595/j.cnki.1000-6753.tces.250683 https://dgjsxb.ces-transaction.com/CN/Y0/V/I/1

[1] 向明旭, 陈泓霏, 曹晓峻, 等. 省间电力中长期交易出清问题多解顺次寻优的高效计算方法[J]. 电工技术学报, 2025, 40(11): 3545-3559.
Xiang Mingxu, Chen Hongfei, Cao Xiaojun, et al.Efficient Sequential Optimization Method for Inter-Provincial Medium-and Long-Term Power Transaction Clearing Problem under Multiple-Solution Scenarios[J]. Transactions of China Electrotechnical Society, 2025, 40(11): 3545-3559.
[2] 高倩, 杨知方, 李文沅. 电力系统混合整数线性规划问题的运筹决策关键技术综述与展望[J]. 电工技术学报, 2024, 39(11): 3291-3307.
Gao Qian, Yang Zhifang, Li Wenyuan.Prospect on Operations Research for Mixed-Integer Linear Programming Problems in Power Systems[J]. Transactions of China Electrotechnical Society, 2024, 39(11): 3291-3307.
[3] 陈启鑫, 房曦晨, 郭鸿业, 等. 电力现货市场建设进展与关键问题[J]. 电力系统自动化, 2021, 45(06): 3-15.
Chen Qixin, Fang Xichen, Guo Hongye1, et al. Progress and Key Issues for Construction of Electricity Spot Market[J]. Automation of Electric Power Systems, 2021, 45(06): 3-15.
[4] Chen Yonghong, Casto A, Wang Fengyu, et al.Improving Large Scale Day-Ahead Security Constrained Unit Commitment Performance[J]. IEEE Transactions on Power Systems, 2016, 31(6): 4732-4743.
[5] 付聪, 王砚平, 刘俊磊, 等. 基于辅助优化问题的安全约束机组组合约束削减方法[J]. 电力系统保护与控制, 2021, 49(21): 9-17.
Fu Cong, Wang Yanping, Liu Junlei, et al.Constraint reduction method for security-constrained unit commitment based on an auxiliary optimization problem[J]. Power System Protection and Control, 2021, 49(21): 9-17.
[6] 袁泉, 孙宇军, 张蔷, 等. 考虑安全约束耦合辨识的日前发电计划求解[J]. 电力系统自动化, 2022, 46(21): 143-151.
Yuan Quan,Sun Yujun,Zhang Qiang, et al.Day-ahead Generation Schedule Solving Considering Identification of Security Constraint Coupling[J]. Automation of Electric Power Systems, 2022, 46(21): 143-151.
[7] 王进, 张粒子, 丛野, 等. 应用图论建模输电网的电力现货市场出清模型[J]. 中国电机工程学报, 2024, 44(09): 3429-3440.
Wang Jin, Zhang Lizi, Cong Ye, et al.A Clearing Model of Electricity Spot Market Based on Graph Theory to modeling transmission Network[J]. Proceedings of the CSEE, 2024, 44(09): 3429-3440.
[8] Chen Yonghong, Pan Feng, Holzer J, et al.A High Performance Computing Based Market Economics Driven Neighborhood Search and Polishing Algorithm for Security Constrained Unit Commitment[J]. IEEE transactions on power systems, 2021, 36(1): 292-302.
[9] Ma Ziming, Zhong Haiwang, Xia Qing, et al.A Unit Commitment Algorithm With Relaxation-Based Neighborhood Search and Improved Relaxation Inducement[J]. IEEE transactions on power systems, 2020, 35(5): 3800-3809.
[10] 颜心斐, 钟海旺, 朱灏翔, 等. 基于系统约束诱导割平面的机组组合加速求解算法[J]. 电网技术, 2025, 49(03): 1155-1165.
Yan Xinfei, Zhong Haiwang, Zhu Haoxiang, et al.Inducing Cutting Planes for System Constraints to Accelerate Network-constrained Unit Commitment[J]. Power System Technology, 2025, 49(03): 1155-1165.
[11] 钟海旺, 虞泽宽, 王孟昌, 等. 电力系统优化求解引擎构建及应用[J/OL]. 电力系统自动化, 2025[2025-12-13].https://link.cnki.net/urlid/32.1180.TP.20251125.1656.006.
Zhong Haiwang, Yu Zekuan, Wang Mengchang, et al. Construction and Application of Power System Optimization Engine[J/OL]. Automation of Electric Power Systems, 2025[2025-12-13]. https://link.cnki.net/urlid/32.1180.TP.20251125.1656.006.
[12] 李佩杰, 万海涛, 赵晓慧, 等. 定制化求解机组组合混合整数线性规划模型的固定——推断法[J]. 电力系统保护与控制, 2023, 51(02): 11-21.
Li Peijie, Wan Haitao, Zhao Xiaohui, et al.A customized fix and implicate method for mixed integer linear programming models of unit commitment problems[J]. Power System Protection and Control, 2023, 51(02): 11-21.
[13] Li Peijie, Liao Changtao, Qi Junjian, et al.User-Induced Heuristics for Security-Constrained Unit Commitment: Variable Influence Diving and Variable Significance Neighborhood Search[J]. IEEE Transactions on Power Systems, 2025, 40(4): 3334-3346.
[14] 李佩杰, 卢胜津, 李凌昊,等 .基于分析中心理论的安全约束机组组合问题启发式方法研究[J/OL]. 电网技术, 2025[2025-12-13]. https://doi.org/10.13335/j.1000-3673.pst.2025.0206.
Li Peijie, Lu Shengjin, Li Linghao, et al.A Heuristic Method for Solving Security Constrained Unit Commitment Problem Based on Analysis Center[J/OL]. Power System Technology, 2025[2025-12-13]. https://doi.org/10.13335/j.1000-3673.pst.2025.0206.
[15] Q Huangfu, Hall J A J. Parallelizing the dual revised simplex method[J]. Mathematical programming computation, 2018, 10(1): 119-142.
[16] 邓俊, 韦化, 黎静华, 等. 一种含四类0-1变量的机组组合混合整数线性规划模型[J]. 中国电机工程学报, 2015, 35(11): 2770-2778.
Deng Jun, Wei Hua, Li Jinghua, et al.A Mixed-integer Linear Programming Model Using Four Sets of Binary Variables for the Unit Commitment Problem[J]. Proceedings of the CSEE, 2015, 35(11): 2770-2778.
[17] Achterberg T, Koch T, Martin A.Branching rules revisited[J]. Operations Research Letters, 2005, 33(1): 42-54.
[18] Achterberg T.Conflict analysis in mixed integer programming[J]. Discrete Optimization, 2007, 4(1): 4-20.
[19] Huang Mengyu, Huang Lingying, Zhong Yuxing, et al.MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound[J]. Journal of the Operations Research Society of China (Internet), 2023, 13: 1-55.
[20] Linderoth J T, Savelsbergh M W P. A Computational Study of Search Strategies for Mixed Integer Programming[J]. INFORMS Journal on Computing, 1999, 11(2): 173-187.
[21] Achterberg T.Constraint integer programming[D]. Berlin: Technische Universität, 2007.
[22] Achterberg T.SCIP: solving constraint integer programs[J]. Mathematical Programming Computation, 2009, 1(1): 1-41.
[23] Applegate D, Bixby R, Chvatal V, et al.Finding Cuts in the TSP (A preliminary report)[R]. Center for Discrete Mathematics & Theoretical Computer Science, 1995.
[24] Benichou M, Gauthier J M, Girodet P, et al.Experiments in mixed-integer linear programming[J]. Mathematical Programming, 1971, 1(1):76-94.
[25] Liberto G D, Kadioglu S, Leo K, et al.DASH: Dynamic Approach for Switching Heuristics[J]. European Journal of Operational Research, 2016, 248(3): 943-953.
[26] Enjyu T, Shimabukuro K, Uezato K, et al.A fast technique for unit commitment problem by extended priority list[J]. IEEE Transactions on Power Systems, 2003, 18(2): 882-888.
[27] Zimmerman R D, Murillo-sanchez C E, Thomas R J. MATPOWER: Steady-State Operations, Planning, and Analysis Tools for Power Systems Research and Education[J]. IEEE Transactions on Power Systems, 2011, 26(1): 12-19.