分支定界搜索信息深度引导的电-气互联系统调度决策加速求解方法OA北大核心CSTPCD

The dispatch problem in integrated electricity and gas system is formulated as the mixed-integer linear programming(MILP)form to describe the discrete feature of resources(such as the unit statuses)and nonlinear operation rules(such as the power flow equation,the Weymouth equation,etc.).The optimal solution achieves the best allocation of resources and indicates the security and economic of the integrated electricity and gas system.However,the large-scale integer variables bring the"combinatorial explosion"challenge,even for the state-of-the-art commercial solvers.To address this problem,existing research focuses on the external algorithms,such as reformulating,reducing the scale of constraints/integer variables,etc.However,it is hard to balance the solution efficiency and the error bound guarantees in practice. Therefore,this paper proposes an internal algorithm that is highly combined with the search information in the branch-and-bound process.The distinct advantage of the proposed method is that the unique structure of integrated electricity and gas system is considered along with the abundant information during the solution process.As a result,the proposed method can achieve an acceleration with optimality guaranteed.This paper reviews the MILP formulation of the dispatch problem in integrated electricity and gas system,and focuses on the computational bottleneck,i.e.,the large-scale integer variables introduced by the piecewise linearization structure of the Weymouth equation.Because most of integer variables in the piecewise linearization structure remains zero,this paper proposes to evaluate the potential effective range of integer variables in the optimal solution,based on the branch-and-bound search information. First,the proposed method collects the relaxation solutions during the initial stage of the branch-and-bound process,to build a search information dataset that implies the optimal value of the piecewise linearization structure.The relaxation solutions are easy to obtain,and they provide lower bounds to the current search tree.Therefore,the idea is that if an integer variable of the piecewise linearization always lies in a similar range across the abundant relaxation solutions,it is likely to remain the same pattern in the optimal solution.Second,the k-nearest neighbors regression algorithm is used to estimate the potential effective range of the piecewise linearization structure.Third,the proposed method builds a small-scale MILP model and solves it in parallel to produce a better solution than the main branch-and-bound process.As a result,the redundant search space in the search tree is pruned by the better solution with no accuracy loss and the optimality is guaranteed. In the case study,the effectiveness of the proposed method has been demonstrated in several aspects based on test cases of RTS-GMLC and gas system.First,for different scales of piecewise linearization structures,compared with the commercial solver,the proposed method accelerates the dispatch problem from 1.60 times to 36.90 times(11.28 times on average).The result also shows that with the improvement of the piecewise linearization scale,the computational burden suddenly increases and can be significantly mitigated by the proposed method,which provides a balance between the formulation precision and the computational efficiency.Second,for 30 test cases using different power demands,the proposed method accelerates the dispatch problem from 1.64 times to 13.52 times(4.20 times on average).It shows that the proposed method behaves well in complicated operation conditions.Third,the case study discusses some details of the proposed method,including the feasibility repair,the prediction accuracy,the upper bound convergence,the search tree scale,and time cost of each step,which provides a thoroughly analysis for the proposed method.Finally,a test case is used to demonstrate the effectiveness in the large-scale system. In conclusion,this paper proposes an acceleration algorithm for the dispatch problem in integrated electricity and gas system.The proposed method improves the solution efficiency without the loss of the optimality guarantees,which is promising in practical and provides a novel view on the optimization in power systems.