Accelerated solution of the transmission maintenance schedule problem:a Bayesian optimization approach

0 Introduction

As an important part of power production and operation,the feasibility and rationality of the transmission maintenance schedule will directly affect the security and economy of power plants and power grid companies.In addition,the transmission maintenance schedule will significantly impact the follow-up dispatching decisionmaking process,such as unit commitment and economic dispatching,and then affect the security,reliability,and economy of the entire power system operation.Owing to the limitations of the computing power and optimization algorithm,the traditional decision-making method of the transmission maintenance schedule is extensive.With the increasing scale of the power grid,the traditional optimization method of the transmission maintenance schedule is facing growing problems and challenges.Thus,the electric power industry urgently needs a more reliable and economical decision-making method for transmission maintenance scheduling and an efficient and high-precision solution algorithm.

In terms of the transmission maintenance schedule model,the objective function aims at maximizing the economy and reliability of the schedule.Various optimization models for the transmission maintenance schedule have been proposed[1-5].In[2-5],the model for the transmission line plan problem was presented only from the point of view of operation of the power network control center,while the model proposed in[1]considers the quantitative restriction of personnel and budget constraint.However,many additional factors should be considered in the transmission-line maintenance optimization model.In addition,a two-layer optimization was applied in[6]to construct an annual transmission line maintenance scheduling model,which resolves the contradiction between ensuring transmission capacity and minimizing the influence of maintenance on the power system operation.In[7],a Monte Carlo simulation approach was applied to evaluate the reliability of a transmission system under maintenance.Given the equipment failure probability and its influence on the scheduling cost,the study in[8]proposed a transmission maintenance scheduling model based on risk.

Several methods have been proposed to solve the power system maintenance schedule problem,such as heuristic methods[9-13],dynamic programming[14],and mixed integer programming(MIP)[15-20].

This paper makes the following main contributions:

(1)In view of the energy constraints of the power system and the security constraints of on-site operations,a transmission maintenance scheduling model is proposed to maximize the willingness of the transmission owners regarding maintenance.

(2)A machine learning(ML)approach is presented to solve the transmission maintenance scheduling model efficiently.BO,which optimizes the value of the branching score factor,plays an important role in the size of the branch-and-bound search tree in the solution process.

The remainder of this paper is organized as follows.Section 1 describes the proposed transmission-scheduling model.Section 2 proposes a solution for the model.In Section 3,the IEEE 30-bus system is employed to demonstrate the computational efficiency of the proposed algorithm,which is compared with a conventional branchand-bound algorithm.Section 4 concludes the article.

1 Modeling of the proposed transmission scheduling model.

1.1 Objective

In the environment of power production and operation,the transmission maintenance department usually reports the maintenance information of their transmission lines to the power network control center,including the maintenance time period and the willingness to maintain transmission.On the basis of meeting the maintenance-related constraints and power system operation constraints,the power network control center will arrange all the maintenance equipment in their maintenance willingness interval as far as possible.

Therefore,the model proposed in this paper considers the maintenance willingness of transmission lines as the objective function,as shown in Equation(1).To ensure the reliability and security of the power system operations,the proposed model satisfies the constraints of the power system.

where αit, is a binary integer variable of the transmission maintenance state;αit, = 1 means that transmission line iis off-line for maintenance on day t,and this situation lasts for some days[21].NT is the total maintenance period,and NLis the number of transmission lines for maintenance.The expected earliest start time and expected end time of the maintenance line constitute the maintenance willingness interval.Generally,the maintenance duration is no longer than the maintenance willingness interval.wit, is the maintenance willingness function of the transmission lines,and it indicates the different maintenance willingness of the transmission lines.The values of the maintenance willingness function are based on the priority of the maintenance lines.Generally,the maintenance willingness function of the transmission line is as shown in Equation(2).

where Prit, is the maintenance priority of transmission line j(such as 1,2,3,and so on).The higher the maintenance priority of the transmission line is,the higher of the Prit, values.In general,the maintenance priority of transmission lines is determined by certain rules,such as the urgency of maintenance and length of maintenance time.The value of the maintenance willingness function is 0 while the time period is outside the maintenance willingness interval.

1.2 Constraints

(i)Integrality requirements

To model the transmission line maintenance scheduling problem more precisely,the model introduces three decision variables for every maintenance transmission line every day.The details are as follows:sit, is a binary integer variable of transmission starting maintenance,and sit,= 1 means that transmission line ibegins offline for maintenance on day t.eit, is a binary integer variable,and eit,= 1 means that transmission line iends maintenance on day t-1.The integer constraints are shown below.

(ii)Constraint of coupling of line maintenance decision variables

where,iis transmission line i,and t is maintenance date t.

(iii)Constraint of completion of maintenance of transmission lines

The constraint ensures that the transmission lines must complete maintenance progress within a maintenance period.

(iv)Constraint of maintenance window of transmission lines

where Esit, and Leiare the earliest maintenance start time and the latest maintenance end time,respectively,and Mdiis the duration of the offline maintenance of transmission line i.The constraint ensures that the transmission line power must be cut for maintenance in the time window of the plan of the power system maintenance department.

(v)Constraints on security of transmission line maintenance,including simultaneous and mutual exclusion constraints

where lines s1 and s2 are pairs in the set of transmission lines that must be maintained at the same time.The simultaneous constraint means that the distance between lines s1 and s2 is too close for providing a safe distance between workers and equipment during maintenance,and thus lines s1 and s2 should be off-line for maintenance simultaneously.

where lines d1 and d2 are pairs in the set of transmission lines that must be maintained at different times.The mutual exclusion constraint indicates that the power of lines d1 and d2 cannot be cut at the same time for power system reliability.

(vi)Node power balance constraint

where dkt, represents the load of node k at time t,Fjt, represents the power flow of transmission line j at time t,∀j k( ,·)represents the line set with K as the initial node,and ∀j k(·,)represents the line set with K as the terminal node.

(vii)Branch DC power balance constraint

where Fjt, represents the power flow of transmission line j at time t,θat, is the phase angle of bus a at time t,and θbt, is the phase angle of bus b at time t.

(viii)Line-transmission limit constraints

where Fjmax, is the transmission capacity limit of line j.

2 Solution of the transmission scheduling model

2.1 Problem definition

MIP is a type of programming problem in which one part of the decision variables comprises integer variables,the other part comprises continuous variables,and the objective function and constraints are both linear forms.In particular,if all of the decision variables are integers and the integer variable in the decision variable can only take a value of 0 or 1,this type of problem is called 0-1 MIP,and the specific model is shown in Equation(15).In a power system,it is sometimes necessary to use 0-1 integer variables to represent the state of equipment.Therefore,there are many 0-1 MIP problems,such as the maintenance planning problem,the unit commitment problem,and the power system planning problem[22].

A mixed-integer linear program is an optimization problem of the form

where is called the objective coefficient vector,is the constraint coefficient matrix, is the constraint right-hand-side vector,and C is the set of integer variables.Under this representation,the size of an MIP is typically measured by the number of rows(m)and columns(n)of the constraint matrix.

The linear program problem(16)is the relaxation model of the original MIP model(15).Compared with model(15),model(16)relaxes the integrality constraint and allows xjvalues in the interval[0,1].

When solving model(15),the relaxation model(16)is solved first,and the relaxation problem forms the root of the branch tree.If a solution to the relaxation model(16)respects the original integrality constraint,then it is also a solution to model(15).Otherwise,model(15)may decompose the liner program relaxation into two sub-problems by splitting the feasible region according to a variable that does not respect integrality in the current LP solution x*,

where[xi]land[xi]udenote the floor and ceil functions,respectively.In practice,the two sub-problems differ only from the parent liner program in the variable bounds for xi.

The optimization gap is the difference between the upper and lower bounds of the optimization problem,as in model(15).If the optimal gap is within the acceptable range,the solution process is terminated,and the optimal solution is obtained.Otherwise,the commercial solver will start using the branch-and-bound algorithm.The branch-and-bound algorithm generates a binary search tree[23].

2.2 Branch rules and score function

Based on the branch-and-bound algorithm,various different tactics for selecting the best candidate variable to branch on have been studied for years.In practice,in branching score functions,the variable with the highest score function value is chosen as the variable to branch on[24-27].The scoring function with variable xihaving a score Siis shown in Equation(18).

2.3 Optimization of branching score factor value using BO

Because the value of the score factor σplays an important role in the size of branch-and-bound trees,the optimization of σrequires further research.In this study,we used BO to optimize the value of the branching score factor.

In the progress of BO,a probability model is constructed for the function f(x),and then the model is applied to predict the value x used to calculate the function value in the next step.The principle of BO takes advantage of all the information obtained from the previous evaluation of function f(x).

The Gaussian process(GP)is estimated and updated by the sample points in the BO,and then the new sample points are determined by the selection function.Naturally,research on BO focuses on the GP and the selection function.

2.3.1 Gaussian process(GP)

The GP is used as a prior function in BO.The GP can be conveniently used to specify a very flexible non-linear regression.A GP is a random process,and any finite number of which have joint Gaussian distributions[29].The GP is fully specified by its mean function m(x)and covariance function k x x( ,)′ .We can write the following:

where the GP function f(x)is with the mean function m x( )and the covariance function k x x( ,′).In our case,f(x)is the branching score factor value σ,and x is the negative number of nodes in the branch-and-bound tree in the training set.

where X and f x( )are the training input and output,respectively,and X* and f x*( )are the test input and output,respectively.Note that f x( )istheknownnegative number of nodes created since the last decision in the training MIP instance,and f x*( )is the unknown branching score factor value σof the test transmission maintenance scheduling instance,which can be the best parameter value that minimizes the size of the branch-and-bound tree.The joint distribution of f x( )and f x*( )is shown in Equation(20).

The detailed derivation process of the above formula and the selection of the kernel function and mean function are presented in reference[30].

2.3.2 Acquisition function

With the prior probability distribution,we need to determine the sampling points for updating the prior with the acquisition function,which plays an important role in the BO.The posterior distribution is obtained from the sampling point above,which makes the distribution more suitable for simulating a real situation.Although many acquisition functions are available,the main idea is to balance the exploration and exploitation strategies.The EI criterion was used as the acquisition function in this study,which proved to perform better than the PI criterion[31].EI criterion a(.)is shown below:

2.3.3 Optimization of branching score factor value with BO

The model is trained first to initialize the BO.We then iterate over the following two steps until a specified maximum number of iterations is reached.First,we generate transmission maintenance scheduling based on the network topology of the grid,and the MIP instances are of approximately the same size as the problem to solve at the constraints and integer variables.Second,the generated instances are trained using the BO algorithm.In the BO,the branching score factor value σ,which is randomly generated between 0 and 1,is set as the input,and the number of nodes created since the last decision counted by the solver is set as output.

Then,we compute the number of nodes created since the last decision in the branch-and-bound tree and find the best branching score factor value.First,we generate a branching score factor valueσ.Then,the trained BO model is applied to predict the number of nodes created since the last decision.We then determine the best branching score factor value σbest.

Finally,we initialize the branching score factor value σ with σbestand solve the transmission maintenance scheduling problem.

2.4 Algorithm procedure

(a)Constraints(3)-(15)and objective function(1)are added to the transmission maintenance schedule model.

(b)Some transmission maintenance schedule instances are generated as a training set

(c)The branching score factor is trained using the BO.

(d)The best branching score factor and gap are set to the model.

(e)The transmission maintenance model is solved using the SCIP solver with the parameter set above.

(f)The solution of the MIP model is obtained from the procedure.If the near-optimal solution is acceptable,terminate the procedure;otherwise,go to(e).

(g)Terminate(Fig.1).

Fig.1 Flowchart of the proposed algorithm

3 Experiment

The effectiveness of the proposed model and algorithm was demonstrated in the testing case of the IEEE 30-bus system.The transmission scheduling period was 30 days.Assuming that the maintenance priority for all transmission lines was the same,then the maintenance willingness functions of all transmission lines were 1 in the entire maintenance period.SCIP 7.0,with the SOPLEX 5.0.2 LP solver,was used to solve the LP and MIP problems,and the gap was set to 10e-5.The operating system was Ubuntu 18.04,the code structure was based on Python 3.8,and the computer processor was an Intel(R)Core(TM)i7-10700F @ 2.90 GHz.

3.1 The IEEE 30-bus system

The topology of the IEEE 30-bus system is shown in Fig.2.It is composed of 30 buses,one extra grid,five generation units,20 load units,and 41 transmission lines.The transmission lines that need to be maintained are marked in red in Fig.2.The maintenance-related parameters of the transmission lines are listed in Table 1.The simultaneous maintenance set of transmission lines is summarized in Table 2.The mutual exclusion maintenance set of the transmission lines is indicated in Table 3.

Fig.2 Topology of IEEE 30-bus network

Table 1 Table 1Transmission maintenance schedulefor 30 days

Transmission line Earliest start time Latest end timeDuration 3 10154 6 5 102 9 21292 1121292 1721294 203102

Table 2 Simultaneous maintenance set of transmission lines

setLine s1Line s2Duration 1 8 104

Table 3 Mutual exclusion maintenance set of transmission lines

setLine d1Line d2 1 2 5

The transmission maintenance MIP model includes 450 binary integer variables and 20521 constraints.First,we generated 100 transmission maintenance scheduling instances with three to ten lines based on the network topology of the IEEE 30-bus system.Second,we trained the generated 100 instances using BO.Then,we generated 500 branching score factor valuesσbetween 0 and 1 and used the trained BO model to predict the number of nodes created since the last decision.Then,we found the best branching score factor value σbest=0.06103,as shown in Fig.3.Finally,we initialized the branching score factor value σbestand solved the transmission maintenance scheduling problem.The transmission maintenance schedule optimized using the proposed method is presented in Table 4.

Table 4 Transmission maintenance schedule

Transmission linestart timeend timeMaintenance duration 3 10134 6 5 6 2 9 21222 1121222 1725284 20452

The progress of the BO of the branching score factor value is shown in Fig.3.The “training set” line in the plot is the collected data during the training progress,in which x is the branching score factor during the training progress and y is the number of nodes created since the last decision.The “value function” line is the collected data during the prediction process,in which x is the generated branching score factor and y is the number of nodes created since the last decision predicted by the training model.

Fig.3 Progress of BO of the branching score factor value

To compare the advantages of the algorithm proposed in this paper and the traditional branch-and-bound algorithm,we compared the calculation times of the maintenance schedule with different number of maintenance lines using the two algorithms,as shown in Fig.4.

Fig.4 Calculation times for different number of maintenance lines with the default and proposed methods

From this analysis,we can draw the following conclusions:(1)adding the BO to the original model to optimize the branch and bound parameters increases the calculation speed significantly,and(2)a high calculation accuracy can be maintained.

4 Conclusion

A transmission maintenance schedule model is proposed in this study to improve the reliability and of power system operations.Given that the proposed model is a large-scale MIP model,the proposed algorithm with BO of the value of the branching score factor is used to accelerate the solving speed of the proposed model.The algorithm proposed in this paper is simple and easy to apply and can be improved based on commercial solvers.Theoretical analysis and algorithm verification show that the proposed algorithm can improve the solving efficiency of the MIP model and increase the computing speed to some degree.In addition,the transmission maintenance schedule model constructed in this study can benefit the and economy of power system operations.

Acknowledgements

This work was supported by the National Key Research and Development Program of China(Basic Research Class)(No.2017YFB0903000)and the National Natural Science Foundation of China(No.U1909201).

Declaration of Competing Interest

We have no conflict of interest to declare.