WO2025061009A1 - Constraint set reduction method and system for electric power system optimization problem - Google Patents

Abstract

The present invention relates to the technical field of electric power systems. Disclosed are a constraint set reduction method and system for an electric power system optimization problem. The present method comprises: determining from a preset optimization problem of an electric power system a constraint set to be reduced; taking as nodes participating variables of each constraint to be reduced, and connecting the nodes according to an order relationship between the participating variables, so as to construct a directed order graph; using the in-degree of each node in the directed order graph to perform node topology sorting on all nodes; and traversing the nodes in the directed order graph on the basis of a node topology sorting result, performing redundant-edge elimination processing, and performing constraint reduction on said constraint set on the basis of a redundant-edge elimination processing result. Therefore, relationships between problem constraints and variables are effectively utilized, and the omission of a large number of redundant constraints, which cannot be easily detected, is prevented, thereby facilitating fast solving and improving the solving efficiency.

Description

A constraint reduction method and system for power system optimization problems

This application claims the priority of the Chinese patent application filed with the China Patent Office on September 20, 2023, with application number 202311211715.7 and invention name “A Constrained Aggregate Reduction Method and System for Power System Optimization Problems”, the entire contents of which are incorporated by reference in this application.

Technical Field

The present invention relates to the technical field of power systems, and in particular to a constraint set reduction method and system for power system optimization problems.

Background Art

At present, the resource allocation optimization problem in the electricity spot market needs to be solved by modeling it as a mixed integer programming problem. At the same time, the scale of the problems to be solved in the electricity spot market is getting larger and larger, and the requirements for solution efficiency are becoming more and more stringent. As an important part of the mixed integer programming solver, the pre-solution module can eliminate redundant constraints in the problem, reduce the problem scale, and tighten the feasible domain of the problem, which plays a key role in improving the solution efficiency.

At present, the pre-solution schemes applied to power market optimization problems generally come from the built-in default algorithms of general mathematical programming solvers, mainly including infeasibility detection, tightening of upper and lower bounds of constraints, tightening of constraint coefficients, and various classical reduction methods. Although the above methods are applicable to any mixed integers, in the special optimization scenario of power market optimization, general methods often fail to effectively utilize the complex relationship between problem constraints and variables, resulting in the omission of a large number of redundant constraints that are difficult to detect, which is not conducive to rapid solution and has an adverse impact on solution efficiency.

Summary of the invention

The present invention provides a constraint intensive reduction method and system for power system optimization problems, which solves the technical problem that it is currently difficult to effectively utilize the complex relationship between problem constraints and variables, resulting in the omission of a large number of redundant constraints that are difficult to detect, which is not conducive to rapid solution and has an adverse impact on solution efficiency.

In view of this, a first aspect of the present invention provides a constraint set reduction method for a power system optimization problem, comprising the following steps:

Based on the preset optimization problem of the power system, multiple constraints to be reduced are determined and the constraints to be reduced are constructed. Constraint set;

Take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order of the participating variables to construct a directed order graph;

Performing node topological sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph;

According to the node topology sorting result, each node in the directed order graph is traversed and redundant edge elimination processing is performed, and constraint reduction is performed on the constraint set to be reduced according to the redundant edge elimination processing result.

Preferably, based on a preset optimization problem of the power system, the steps of determining a plurality of constraints to be reduced and constructing a set of constraints to be reduced specifically include:

Determine the constraint set of the power system based on the preset optimization problem of the power system;

Based on the constraint set of the power system, constraints containing two decision variables of 0-1 are screened out as constraints to be reduced, and a constraint set to be reduced is constructed.

Preferably, each participating variable of the constraint to be reduced is taken as a node, and the nodes are connected according to the order relationship of the participating variables, and before the step of constructing a directed order graph, the method further includes:

Mathematically transform each constraint to be reduced in the constraint set to be reduced to obtain participating variables and participating variable order relationships of each constraint to be reduced.

Preferably, the step of performing mathematical deformation on each constraint to be reduced in the constraint set to be reduced to obtain the participating variables and the order relationship of the participating variables of each constraint to be reduced specifically comprises:

Each to-be-reduced constraint in the to-be-reduced constraint set is mathematically transformed to obtain an order constraint, wherein the order constraint is an inequality constraint and the order constraint includes participating variables and an order relationship of the participating variables.

Preferably, the step of performing node topological sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph specifically includes:

Initialize the topological sorted list;

Using a breadth/depth first search algorithm to traverse each node in the directed sequence graph, inserting the node with the smallest in-degree in the directed sequence graph into the topological sorting list;

Based on the node inserted in the topological sorting list, the inserted node and the edge linked to it are deleted from the directed sequence graph, and the in-degree of each node in the directed sequence graph is updated;

Based on the updated in-degree of the remaining nodes in the directed sequence graph, re-execute the The step of inserting the node with the smallest in-degree in the directed sequence graph into the topological sorting list is performed until all the nodes in the directed sequence graph are inserted into the topological sorting list in sequence, thereby obtaining a node topological sorting result.

Preferably, the steps of traversing each node in the directed ordered graph and performing redundant edge elimination processing according to the node topological sorting result, and performing constraint reduction on the constraint set to be reduced according to the redundant edge elimination processing result specifically include:

Traversing each node in the directed order graph according to the node topological sorting result and performing redundant edge elimination processing to obtain a transitive reduction graph;

Comparing the transitive reduction graph with the directed order graph to determine the reduced redundant edges;

The corresponding to-be-reduced constraints in the to-be-reduced constraint set are reduced according to the reduced redundant edges.

Preferably, the step of traversing each node in the directed ordered graph and performing redundant edge elimination processing according to the node topological sorting result to obtain the transfer reduction graph specifically includes:

Traversing each node in the directed sequence graph in turn according to the node topological sorting result, and determining the edges connecting two nodes in the directed sequence graph;

According to the node topological sorting result, traverse each edge e=(u,v) in the directed sequence graph in turn, where e represents an edge, u represents a departure node, and v represents an arrival node, and determine whether there are other edges in the directed sequence graph that can go from the departure node u to the arrival node v except the edge e;

If it is determined that there are other edges in the directed sequence graph except edge e that can reach the arrival node v from the departure node u, then edge e is deleted from the directed sequence graph to obtain a transitive reduction graph.

Preferably, comparing the transitive reduction graph with the directed order graph to determine the step of reducing redundant edges specifically includes:

The transitive reduction graph is compared with the directed order graph, and edges that exist in the directed order graph but do not exist in the transitive reduction graph are screened out as reduced redundant edges.

Preferably, the step of reducing the corresponding to-be-reduced constraints in the to-be-reduced constraint set according to the reduced redundant edges specifically includes:

Obtaining nodes on both sides of the reduced redundant edge;

Based on the mapping relationship between nodes and participating variables, the corresponding participating variables and their corresponding to-be-reduced constraints are matched in the to-be-reduced constraint set through the nodes on both sides of the reduced redundant edge. bundle;

The matched constraints to be reduced are deleted from the set of constraints to be reduced.

In a second aspect, the present invention further provides a constraint set reduction system for power system optimization problems, comprising:

A reduction constraint acquisition module is used to determine multiple constraints to be reduced based on a preset optimization problem of the power system and to construct a set of constraints to be reduced;

A graph construction module is used to take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order relationship of the participating variables to construct a directed order graph;

A node topology sorting module is used to perform node topology sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph;

The constraint reduction module is used to traverse each node in the directed order graph according to the node topology sorting result and perform redundant edge elimination processing, and perform constraint reduction on the constraint set to be reduced according to the redundant edge elimination processing result.

In a third aspect, the present invention further provides an electronic device, comprising a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory communicate with each other via the communication bus;

Memory, used to store computer programs;

The processor is used to implement the above method steps when executing the program stored in the memory.

In a fourth aspect, the present invention further provides a computer-readable storage medium, wherein the computer-readable storage medium stores a computer program, and the computer program implements the above-mentioned method steps when executed by a processor.

It can be seen from the above technical solutions that the present invention has the following advantages:

The present invention determines a set of constraints to be reduced from a preset optimization problem of an electric power system, connects participating variables of each constraint to be reduced as nodes according to the order relationship of the participating variables, constructs a directed order graph, performs node topology sorting on all nodes using the in-degree size of each node in the directed order graph, traverses each node in the directed order graph according to the node topology sorting result and performs redundant edge elimination processing, and performs constraint reduction on the set of constraints to be reduced according to the redundant edge elimination processing result, thereby effectively utilizing the relationship between problem constraints and variables, avoiding missing a large number of redundant constraints that are difficult to detect, facilitating rapid solution, and improving solution efficiency.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a schematic diagram of the output range of a hydropower unit;

Figure 2 is a schematic diagram of the order relationship of the variables on both sides of the constraint;

FIG3 is a flow chart of a constraint set reduction method for a power system optimization problem provided by an embodiment of the present invention;

FIG4 is a schematic diagram of eliminating redundant edges in a directed sequence graph provided by an embodiment of the present invention;

FIG5 is a flow chart of a constraint set reduction method for a power system optimization problem provided by another embodiment of the present invention;

FIG6 is a schematic diagram of an IEEE6 node connection topology structure provided in an embodiment of the present invention;

FIG7 is a directed sequence graph provided by an embodiment of the present invention;

FIG8 is a schematic diagram of a topological sorting process provided by an embodiment of the present invention;

FIG9 is a transfer reduction diagram provided by an embodiment of the present invention;

FIG10 is a simplified directed sequence graph provided by an embodiment of the present invention;

FIG11 is a schematic diagram of the structure of a constraint set reduction system for a power system optimization problem provided by an embodiment of the present invention.

DETAILED DESCRIPTION

In order to enable those skilled in the art to better understand the scheme of the present invention, the technical scheme in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.

At present, the pre-solution solutions applied to power market optimization problems generally come from the built-in default algorithms of general mathematical programming solvers, mainly including infeasibility detection, tightening of upper and lower bounds of constraints, tightening of constraint coefficients, and various classical reduction methods. Although the above methods are applicable to any mixed integers, in the special optimization scenario of power market optimization, general methods are often difficult to effectively use. The complex relationship between problem constraints and variables may lead to the omission of a large number of redundant constraints that are difficult to detect, which is not conducive to rapid solution and has an adverse impact on solution efficiency.

Among them, the unit combination problem is one of the most critical issues in the electricity market clearing. Its purpose is to determine the start and stop status of each unit. Due to the complexity of the actual problem scenario, a large number of constraints need to be introduced into the mathematical model of the unit combination problem to describe the complex business logic. These constraints are usually an important factor in determining the efficiency of problem solving.

In most cases, the fewer the number of constraints used to describe the same business logic, the more efficient the mixed integer programming solver is in solving the problem. Especially when the root node of the problem is difficult to solve, if a more compact and concise representation of the feasible domain of the problem can be found, the solver can make full use of this property to speed up the calculation of subsequent modules.

In the unit combination problem, unit start and stop and hydropower vibration zone are the basic business logic. The constraints used to characterize this logic account for a large proportion of all model constraints, which increases the scale of the optimization problem and affects the efficiency of solving the optimization problem.

For example, in the unit start-stop constraint, the unit start-stop constraint can be represented by three types of variables, including I, W and Y, where I represents the start-stop status of each unit at different time periods, I is the direct decision variable of the optimization problem, W and Y represent the start-stop decision of each unit at different time periods, and these three types of variables jointly model the start-stop constraint of the unit combination problem as follows:
W _i,t -Y _i,t =I _i,t -I _i,t-1 ;
Wi _,t - _Yi,t≤1 ;

Where i is the sequence number of the unit, t is the decision dimension in time, Wi _,t is the start state decision of unit i in period t, Yi _,t is the stop state decision of unit i in period t, Ii _,t is the start and stop state of unit i in period t, and Ii _,t-1 is the start and stop state of unit i in period t-1.

Among them, the first constraint describes the change of the unit's start-up or shutdown status when the unit makes a startup or shutdown decision; the second constraint restricts the unit from being started and shut down at the same time.

For the sake of convenience, we omit the subscript of the time dimension and transform the second constraint expression into the following form:

The constraint of _Wi + _Yi ≤1.

In addition to the basic constraint of unit start-up and shutdown, the characterization of hydropower vibration zone in the power market will also introduce similar constraints: unlike thermal power units, the output range of hydropower units is not continuous, as shown in Figure 1 As shown in Figure 1, the output range of the hydropower unit is shown, which requires us to introduce a 0-1 variable Indicates whether the output of the hydropower unit is within a certain range, and introduces the following constraints to ensure that the output of the unit is within a certain range. The constraint expression is:

In the formula, S represents the number of units.

Without loss of generality, we can add auxiliary variables to simplify the sum of multiple 0-1 variables, and then use x to uniformly represent the above two types of constraints as follows:

The constraints are as follows, where x _i and x _j are the start and stop decisions of the units at the same time. Then, by adjusting the above constraints, This auxiliary constraint can be further rewritten as follows:

The order constraints are: represents a start-stop decision different from _xi .

In the order constraint, the direction of the inequality sign determines the logical order of the variables on both sides of the constraint. The relationship between the direction of the inequality sign and the order of the variables on both sides of the constraint is set by yourself, such as The order relationship of the variables on both sides of the constraint is shown in Figure 2.

In the optimization problem of electricity market clearing, the following phenomenon can be observed: when there are three or more variables with a chronological order, there are often redundant logical relationships in the mathematical model. Taking the three-variable constraint as an example, among the three constraints x ₁ ≤x ₂ ,x ₂ ≤x ₃ ,x ₁ ≤x ₃ , x ₁ ≤x ₂ ,x ₂ ≤x ₃ can be implicitly expressed as x ₁ ≤x ₃ through the transitivity of inequalities, so we can remove it from the problem without affecting its equivalence with the original problem. This reduction process is also called the transitive reduction method.

Although the reduction process of the three constraints of the three variables mentioned above is intuitively simple, it is very difficult to manually find all the constraints that can be transferred and reduced when the number of variables and constraints is huge. For example, in the unit combination model of the southern regional power spot market, the variables and constraints are all at the million level. At this time, it is difficult to identify the reducible constraints by manual logical deduction. Therefore, we need to propose a systematic The solution is to use computers to complete the reduction task. However, since transitive reduction requires considering the relationship between multiple constraints at the same time, it is difficult to directly implement logical reasoning at the algebraic level and traverse each combination in a computer, and general methods often fail to effectively utilize the complex relationship between problem constraints and variables, resulting in the omission of a large number of redundant constraints that are difficult to detect, which is not conducive to rapid solution and has an adverse impact on solution efficiency.

To this end, referring to FIG. 3 , a constraint set reduction method for a power system optimization problem provided by the present invention includes the following steps 101 to 104, specifically including the following steps:

101. Based on the preset optimization problem of the power system, multiple constraints to be reduced are determined, and a set of constraints to be reduced is constructed.

Among them, the preset optimization problem of the power system is built based on the variables of the power system. The optimization problem generally includes an objective function and constraints, and determines the set of order constraints that need to be reduced.

102. Take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order relationship of the participating variables to construct a directed order graph.

Among them, the participating variables and the participating variable order relationship are obtained based on the variables in the constraint formula to be reduced after determining the constraint to be reduced, wherein the participating variables refer to the variables participating in the decision-making in the constraint to be reduced, and the participating variable order relationship refers to the order relationship between the participating variables. The participating variable order relationship can be mapped based on the size relationship between the participating variables, and the participating variable order relationship is set based on the size relationship between the participating variables.

Specifically, the variables participating in the constraints to be reduced can be used as nodes, and directed edges can be connected between the nodes according to the order of the participating variables. After construction according to the above rules, a directed graph can be obtained with the number of nodes equal to the number of variables and the number of edges equal to the number of constraints. Assuming that there is no loop in the graph that can be obtained (otherwise the series of inequality constraints that form the loop will be converted into equations), a directed acyclic graph is formed based on graph theory.

103. Perform node topological sorting on all nodes in the directed sequence graph according to the in-degree of each node in the directed sequence graph.

In this embodiment, for a directed ordered graph G=(R, E), R and E both represent nodes, and the in-degree of each node R is defined as the number of edges entering R; the out-degree is defined as the number of edges departing from R.

104. According to the node topology sorting result, each node in the directed order graph is traversed and redundant edge elimination is performed, and according to the redundant edge elimination result, constraint reduction is performed on the constraint set to be reduced.

It should be noted that the transitive reduction scheme converts the logical reasoning required in the transitive reduction method into the problem of eliminating redundant edges in a directed order graph, as shown in Figure 4. Figure 4 illustrates the elimination of redundant edges in a directed order graph, thereby eliminating the connecting edges between variables _x1 and _x4 . After the eliminated connecting edges are mapped to the set of constraints to be reduced, the edges that can be deleted without changing the reachability of the graph correspond to the redundant reducible parts in the constraint set.

It should be noted that the present invention determines the set of constraints to be reduced from the preset optimization problem of the power system, connects the participating variables of each constraint to be reduced as nodes according to the order relationship of the participating variables, constructs a directed order graph, and uses the in-degree size of each node in the directed order graph to perform node topological sorting on all nodes. According to the node topological sorting result, each node in the directed order graph is traversed and redundant edge elimination is performed, and constraint reduction is performed on the constraint set to be reduced according to the redundant edge elimination result, thereby effectively utilizing the relationship between the problem constraints and the variables, avoiding missing a large number of redundant constraints that are difficult to detect, facilitating rapid solution, and improving solution efficiency.

The above is a detailed description of an embodiment of a constraint set reduction method for a power system optimization problem provided by the present invention. The following is a detailed description of another embodiment of a constraint set reduction method for a power system optimization problem provided by the present invention.

For ease of understanding, please refer to FIG5 , a constraint set reduction method for a power system optimization problem provided by another embodiment of the present invention includes the following steps:

Based on a preset optimization problem of the power system, multiple constraints to be reduced are determined, and a set of constraints to be reduced is constructed.

In one example, step 201 specifically includes:

2011. Determine the constraint set of the power system based on the preset optimization problem of the power system.

2012. Based on the constraint set of the power system, the constraints containing two decision variables of 0-1 are selected as the constraints to be reduced, and the constraint set to be reduced is constructed.

It should be noted that the present invention performs transitive reduction on constraints containing two decision variables of 0-1, wherein the constraints of the two decision variables of 0-1 refer to that the decision is 0 or 1, and different decisions cannot be made at the same time. Before the general solver computer group combines the problems, the trivial pre-solution method will be used to reduce the model size and determine the values of some 0-1 variables in advance.

202. Perform mathematical transformation on each constraint to be reduced in the constraint set to obtain participating variables and participating variable order relations of each constraint to be reduced.

It should be noted that each constraint to be reduced in the constraint set to be reduced is mathematically transformed through mathematical operations and transformations, such as the participating variables in the power on/off constraint W ₁ +Y ₁ ≤1 are W ₁ and Y ₁ , and a mapping relationship between constraints and variables is established in the computer for subsequent establishment of an ordered directed sequence graph.

In one achievable manner, each to-be-reduced constraint in the to-be-reduced constraint set is mathematically transformed to obtain an order constraint, wherein the order constraint is an inequality constraint and includes participating variables and an order relationship of the participating variables.

It should be noted that after obtaining the set of constraints to be reduced, the constraints to be reduced need to be simplified in form by introducing auxiliary constraints and merging similar terms and equivalent mathematical transformations, so as to convert the constraints to be reduced into order constraints of inequalities involving only the participating variables. In the order constraints, the direction of the inequality sign determines the logical order of the variables on both sides of the constraint. The relationship between the direction of the inequality sign and the order relationship of the variables on both sides of the constraint is set by yourself, such as The order relationship of the variables on both sides of the constraint is shown in Figure 2.

In an electric power optimization problem, there can be multiple constraints containing two decision variables of 0-1. For multiple constraints containing two decision variables of 0-1, the multiple constraints to be reduced can be sorted according to the number of decision variables. In general examples, they are sorted in ascending order, that is, sorted according to the difficulty of constraint reduction. The sorted multiple constraints to be reduced form a constraint set to be reduced. In practical applications, if there is a constraint that contains a variable in the constraint set to be reduced, the format is similar to the following:

Wherein, i represents the unit number, S represents the number of units, _xi represents the 0-1 decision variable of unit i, _xi = 0 or 1, y represents other decision variables, and b represents the right value of the constraint.

The constraint format is similar to the following:

And the mathematical transformation is as follows:

After completing the above processing, a constraint containing only two decision variables can be obtained.

203. Take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order relationship of the participating variables to construct a directed order graph.

It should be noted that step 203 in this embodiment is consistent with step 101 in the aforementioned embodiment and will not be described in detail here.

204. Perform node topological sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph.

Specifically, step 204 includes:

2041. Initialize the topologically sorted list.

Among them, after the topological sorting list is initialized, the topological sorting list is empty.

2042. Use the breadth/depth first search algorithm to traverse each node in the directed ordered graph, and insert the node with the smallest in-degree in the directed ordered graph into the topological sorted list.

Here, in-degree is defined as the number of edges connected to a node.

2043. Based on the node inserted in the topological sort list, the inserted node and the edge linked to it are deleted from the directed sequence graph, and the in-degree of each node in the directed sequence graph is updated.

It should be noted that after deleting a node and the edges to which it is linked, the in-degrees of the remaining nodes in the directed sequence graph will also be updated.

2044. Based on the in-degrees of the remaining nodes in the updated directed sequence graph, re-execute the step of inserting the node with the smallest in-degree in the directed sequence graph into the topological sorting list until all the nodes in the directed sequence graph are inserted into the topological sorting list in sequence, thereby obtaining a node topological sorting result.

Among them, if all the nodes in the directed sequence graph are not empty, then continue to insert the node with the smallest in-degree in the directed sequence graph into the topological sorting list until all the nodes in the directed sequence graph are empty, and the order in which the nodes are inserted into the topological sorting list in turn is the node topological sorting result.

In an example, given a directed graph G, the node topology sorting process is: select a node u with an in-degree of 0 in the directed graph G and add it to the sorting. Then, for each node v that has not been sorted, if there is a directed edge from u to v, we reduce the in-degree of node v by one. Repeat the above process until all nodes are sorted. The sorting result is the node topology. Sort the results.

205. According to the node topological sorting result, each node in the directed order graph is traversed and redundant edges are eliminated to obtain a transitive reduction graph.

Specifically, step 205 includes:

2051. According to the node topological sorting result, each node in the directed sequence graph is traversed in turn to determine the edges connecting each two nodes in the directed sequence graph.

2052. According to the node topological sorting result, traverse each edge e=(u,v) in the directed sequence graph in turn, where e represents the edge, u represents the starting node, and v represents the arrival node, and determine whether there are other edges in the directed sequence graph except the edge e that can go from the starting node u to the arrival node v.

2053. If it is determined that there are other edges in the directed sequence graph except edge e that can go from the departure node u to the arrival node v, then delete edge e from the directed sequence graph to obtain a transitive reduction graph.

It should be noted that if in the directed sequence graph there are edges other than edge e that can go from the departure node u to the arrival node v, then edge e is a logically redundant edge, that is, a logically redundant constraint in the constraint system.

In an example, suppose there are three nodes u, v, and z in a directed order graph, and the edge relationships between the three are u>v>z and u>z. Since node u can already reach z through the path u>v>z, and since u>v or v>z cannot be deleted because u cannot reach v or v cannot reach z after deleting the two paths u>v or v>z, the two paths u>v or v>z cannot be deleted. The edge u>z is an extra edge and can be deleted, which means that the edge u>z is a logically redundant edge, which is a logically redundant constraint in the constraint system.

In another example, a transitive reduction graph can also be constructed based on top-down transitive reduction and bottom-up transitive closure. Specifically, the construction of the transitive closure starts from the empty edge set E’ and continuously adds new edges. For example, for each node u traversed by topological sorting, for each node v that can be reached by u in the set E, if there is no path from u to v in the set E’, then (u,v) is added to the set E’.

206. Compare the transitive reduction graph with the directed order graph to determine the reduced redundant edges.

It should be noted that, based on graph theory, when we obtain the transitive reduction graph _Gt , we can map its edge set back to the constraint set. At this time, since the directed order graph G and the transitive reduction graph _Gt have the same transitive closure, the feasible domain range represented by the constraint does not change. The cardinality of the edge set of the reduction graph _Gt is generally always smaller than that of the directed order graph G. The transitive reduction graph _Gt is also called the transitive reduction graph of the directed order graph G.

At the same time, after obtaining the transitive reduction graph _Gt , it is compared with the directed order graph G to find out the edges that exist in the original order graph but not in the reduced order graph, which are the reduced redundant edges.

In one achievable manner, the transitive reduction graph is compared with the directed order graph, and edges that exist in the directed order graph but not in the transitive reduction graph are screened out as reduced redundant edges.

207. Reduce the corresponding to-be-reduced constraints in the to-be-reduced constraint set according to the reduced redundant edges.

Specifically, step 207 includes:

2071. Obtain the nodes on both sides of the reduced redundant edge.

2072. Based on the mapping relationship between nodes and participating variables, the corresponding participating variables and their corresponding to-be-reduced constraints are matched in the to-be-reduced constraint set by reducing the nodes on both sides of the redundant edge.

It should be noted that in the process of forming a directed order graph, the nodes are connected based on the participating variables, so there is a mapping relationship between the nodes and the participating variables. After determining the nodes on both sides of the reduced redundant edges, the corresponding participating variables and their corresponding constraints to be reduced can be matched in the set of constraints to be reduced based on the mapping relationship between the nodes and the participating variables.

2073. Delete the matched constraints to be reduced from the set of constraints to be reduced.

In order to more clearly illustrate the above-mentioned constraint set reduction process of the power system optimization problem, a practical example of power system unit combination is given below for illustration in combination with a constraint set reduction method for the power system optimization problem provided by the present invention.

As shown in FIG6 , FIG6 illustrates an IEEE 6-node connection topology structure. A constraint set reduction method for a power system optimization problem provided by the present invention is applied to a system of an IEEE 6-node unit combination problem. The system is formed by connecting 6 buses Bus1, Bus2, Bus3, Bus4, Bus5, Bus6, 3 units G ₁ , G ₂ , G ₃ , 3 load nodes D ₁ , D ₂ , D ₃ and 11 tie lines. Specific data parameters are shown in Tables 1 to 3.

Table 1 Unit data

Table 2 Tie line data

Table 3 Hourly load data

The mathematical model of the unit commitment problem includes objective function and constraints.

Among them, the objective function is:

Where Z is the operating cost, T is the number of optimization periods, PC _i (P _i,t ) is the unit operation quotation, I _i,t is the unit start and stop status, SU _i,t and SD _i,t are the unit startup and shutdown costs, respectively.

The following constraints are considered based on the lowest unit operating cost, including:

1) The node load balancing constraint is:

Among them, this constraint requires that the load of each node can be satisfied, I _b is all the units contained in node b, P _i,t is the power of unit i at time t, ^j is the tie line number, is the tie line of input node b, is the tie line leaving node b, TL _j,t is the output of tie line j in period t, and D _b,t is the load of node b in period t.

2) The unit output constraint is:

This constraint requires that if unit i is turned on in time period t, the output range is met, and if it is turned off _, the output is 0. are the minimum and maximum output of the unit respectively.

3) The unit climbing constraint is:

This constraint requires that the output change of unit i meets the unit climbing range requirements, and it can only be shut down when it climbs to the minimum output. Among them, ir _i and dr _i are the climbing rate and the descending rate of unit i respectively.

4) The minimum start and stop time constraint of the unit is:

This constraint requires that each time the unit i is turned on or off, it must be kept on for a certain minimum on time and minimum off time. Among them, τ is the maximum start-stop time, and _Ti ^down and _Ti ^up are the minimum off time and minimum on time of unit i, respectively.

5) Tie line output constraints

This constraint requires that the tie line output must meet a certain _output range. are the minimum and maximum outputs of tie line j respectively.

This patented method focuses on removing redundancy that only contains 0-1 variables, which in this example is the minimum start-stop time constraint. Before the general solver computer group combines the problem, the trivial pre-solving method is used to reduce the model size and determine the values of some 0-1 variables in advance. In the 6-node system in this example, due to the small scale, some 0-1 variables can be determined in advance through the following business logic to simulate the process of trivial pre-solving of the general solver.

Use business logic to determine 0-1 variables: In the load data table, at 18, 19, and 20, node 4 and load 1 require a power greater than 160MW. At the same time, node 4 is connected by only two paths, path 1-2-4 and path 1-4. The upper limit of all tie lines in the two paths is 160MW. Node 1 contains unit G ₁ and node 2 contains unit G _2. If G ₁ is shut down at 18, 19, and 20, load D ₁ cannot meet the load demand through the 160MW upper limit of the tie line 2-4. Therefore, unit G ₁ needs to start up and output at 18, 19, and 20, that is, I _1,18 =I _1,19 =I _1,20 =1. However, the state of unit G ₂ cannot be determined because G ₁ can meet the demand of load D ₁ through two paths 1-2-4 and 1-4 respectively.

After obtaining the above preprocessing information, the patented method can delete redundant constraints for the following constraints.
I _1,11 -I _1,12 ≤1-I _1,13
I _1,11 -I _1,12 ≤1-I _1,14
I _1,11 -I _1,12 ≤1-I _1,15
I _1,12 -I _1,13 ≤1-I _1,14
I _1,12 -I _1,13 ≤1-I _1,15
I _1,12 -I _1,13 ≤1-I _1,16
I _1,13 -I _1,14 ≤1-I _1,15
I _1,13 -I _1,14 ≤1-I _1,16
I _1,13 -I _1,14 ≤1-I _1,17
I _1,14 -I _1,15 ≤1-I _1,16
I _1,14 -I _1,15 ≤1-I _1,17
I _1,14 -I _1,15 ≤1-I _1,18
I _1,15 -I _1,16 ≤1-I _1,17
I _1,16 -I _1,17 ≤1-I _1,18
I _1,16 -I _1,17 ≤1-I _1,19
I _1,16 - _{I 1,17} ≤1-I _1,20 ;

By combining like terms and equivalent mathematical transformation and simplifying, we finally get the following inequality on the right side:
I _1,11 -I _1,12 ≤1-I _1,13
I _1,11 -I _1,12 ≤1-I _1,14
I _1,11 -I _1,12 ≤1-I _1,15
I _1,12 -I _1,13 ≤1-I _1,14
I _1,12 -I _1,13 ≤1-I _1,15
I _1,12 -I _1,13 ≤1-I _1,16
I _1,13 -I _1,14 ≤1-I _1,15
I _1,13 -I _1,14 ≤1-I _1,16
I _1,13 -I _1,14 ≤1-I _1,17
I _1,14 -I _1,15 ≤1-I _1,16
I _1,14 -I _1,15 ≤1-I _1,17
I _1,15 -I _1,16 ≤1-I _1,17
1-I _1,15 ≤1-I _1,14
1-I _1,16 ≤1-I _1,15
1-I _1,17 ≤1-I _1,16 ;

Now we need to replace the above system variables with each constraint based on the patent method. Quantity, which is defined as:
α _t =I _1,t -I _1,t+1
β _t =1-I _1,t ;

So the above inequality becomes:
α ₁₁ ≤β ₁₃
α ₁₁ ≤β ₁₄
α ₁₁ ≤β ₁₅
α ₁₂ ≤β ₁₄
α ₁₂ ≤β ₁₅
α ₁₂ ≤β ₁₆
α ₁₃ ≤β ₁₅
α ₁₃ ≤β ₁₆
α ₁₃ ≤β ₁₇
α ₁₄ ≤β ₁₆
α ₁₄ ≤β ₁₇
α ₁₅ ≤β ₁₇
β ₁₅ ≤ _{β 14}
β ₁₆ ≤β ₁₅
β ₁₇ ≤ _{β 16} ;

According to the order relationship of the variables in the above inequality, a directed order graph can be constructed as shown in FIG7 .

Then, nodes are continuously deleted according to the in-degree of the directed graph nodes to obtain a topological sort. The topological sorting process is shown in FIG8 .

Then, each node is traversed according to the topological sorting to obtain the transitive reduction graph as shown in FIG9 .

After completing the final transitive reduction graph, the deleted connections can be checked. These connections are the edges whose redundant constraints can be deleted, as shown in FIG10 . FIG10 illustrates a simplified directed order graph, in which the dotted lines are the edges that can be deleted.

Then the edges that can be deleted are mapped to the constraint set, so that the inequality system after redundant filtering can be obtained as follows:
I _1,11 -I _1,12 ≤1-I _1,13
I _1,11 -I _1,12 ≤1-I _1,15
I _1,12 -I _1,13 ≤1-I _1,16
I _1,13 -I _1,14 ≤1-I _1,17
I _1,14 -I _1,15 ≤1-I _1,17
I _1,15 -I _1,16 ≤1-I _1,17
I _1,14 ≤I _1,15
I _1,15 ≤I _1,16
I _1,16 ≤I _1,17 ;

Finally, six inequality constraints were deleted through this method. Compared with the existing general methods, this method has higher applicability for power optimization problems and can identify a large number of redundant constraints that general methods cannot identify. In the actual power system production environment, the reduction effect of this scheme is significant. At present, in practical applications, among the overall constraints (more than 500,000), the method can effectively delete more than 5% of the redundant order constraints on average, and the computational efficiency is improved by about 21%.

In practical applications, a SCUC problem for six units with 24 periods of time corresponds to some unit on/off constraints, in which three redundant constraints are hidden. At this time, manual logical deduction is completely unable to identify the reducible constraints. If a constraint set reduction method for power system optimization problems is proposed by the present invention, transfer reduction is performed based on a transfer order graph, thereby easily reducing the three redundant constraints.

The above is a detailed description of an embodiment of a constraint set reduction method for a power system optimization problem provided by the present invention. The following is a detailed description of an embodiment of a constraint set reduction system for a power system optimization problem provided by the present invention.

For ease of understanding, please refer to FIG. 11 . The present invention further provides a constraint set reduction system for power system optimization problems, including:

The reduction constraint acquisition module 100 is used to determine a plurality of constraints to be reduced based on a preset optimization problem of the power system, and to construct a set of constraints to be reduced;

A graph construction module 200 is used to take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order relationship of the participating variables to construct a directed order graph;

The node topology sorting module 300 is used to sort the nodes in the directed sequence graph according to the in-degree of each node. Perform node topological sorting on all nodes in the directed order graph;

The constraint reduction module 400 is used to traverse each node in the directed order graph according to the node topology sorting result and perform redundant edge elimination processing, and perform constraint reduction on the constraint set to be reduced according to the redundant edge elimination processing result.

The present invention also provides an electronic device, comprising a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory communicate with each other via the communication bus;

Memory, used to store computer programs;

The processor is used to implement the above method steps when executing the program stored in the memory.

The present invention also provides a computer-readable storage medium, in which a computer program is stored. When the computer program is executed by a processor, the above method steps are implemented.

Those skilled in the art can clearly understand that, for the convenience and brevity of description, the specific working processes of the above-described system, electronic device and computer-readable storage medium can refer to the corresponding processes in the aforementioned method embodiments and will not be repeated here.

In the several embodiments provided by the present invention, it should be understood that the disclosed systems, electronic devices, computer-readable storage media and methods can be implemented in other ways. For example, the device embodiments described above are only schematic. For example, the division of modules is only a logical function division. There may be other division methods in actual implementation. For example, multiple modules or components can be combined or integrated into another system, or some features can be ignored or not executed. Another point is that the mutual coupling or direct coupling or communication connection shown or discussed can be through some interfaces, indirect coupling or communication connection of devices or modules, which can be electrical, mechanical or other forms.

The modules described as separate components may or may not be physically separated, and the components shown as modules may or may not be physical modules, that is, they may be located in one place or distributed on multiple network modules. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution of this embodiment.

In addition, each functional module in each embodiment of the present invention may be integrated into one processing module, or each module may exist physically separately, or two or more modules may be integrated into one module. The above-mentioned integrated modules may be implemented in the form of hardware or software. It is implemented in the form of software function modules.

If the integrated module is implemented in the form of a software function module and sold or used as an independent product, it can be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present invention, in essence, or the part that contributes to the prior art, or all or part of the technical solution can be embodied in the form of a software product. The computer software product is stored in a storage medium, including a number of instructions for executing all or part of the steps of the various embodiments of the method of the present invention through a computer device (which can be a personal computer, server, or network device, etc.). The aforementioned storage medium includes: U disk, mobile hard disk, read-only memory (full name in English: Read-Only Memory, English abbreviation: ROM), random access memory (full name in English: Random Access Memory, English abbreviation: RAM), disk or optical disk and other media that can store program codes.

The above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit the same. Although the present invention has been described in detail with reference to the aforementioned embodiments, a person skilled in the art should understand that the technical solutions described in the aforementioned embodiments may still be modified, or some of the technical features may be replaced by equivalents. However, these modifications or replacements do not deviate the essence of the corresponding technical solutions from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (12)

A constraint set reduction method for power system optimization problem, characterized by comprising the following steps: Based on the preset optimization problem of the power system, multiple constraints to be reduced are determined, and a set of constraints to be reduced is constructed; Take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order of the participating variables to construct a directed order graph; Performing node topological sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph; According to the node topology sorting result, each node in the directed order graph is traversed and redundant edge elimination processing is performed, and constraint reduction is performed on the constraint set to be reduced according to the redundant edge elimination processing result. The constraint set reduction method for power system optimization problem according to claim 1 is characterized in that, based on the preset optimization problem of the power system, a plurality of constraints to be reduced are determined, and the steps of constructing the constraint set to be reduced specifically include: Determine the constraint set of the power system based on the preset optimization problem of the power system; Based on the constraint set of the power system, constraints containing two decision variables of 0-1 are screened out as constraints to be reduced, and a constraint set to be reduced is constructed. The constraint set reduction method for power system optimization problem according to claim 1 is characterized in that the participating variables of each constraint to be reduced are taken as nodes, and the nodes are connected according to the order relationship of the participating variables, and before the step of constructing a directed order graph, it also includes: Mathematically transform each constraint to be reduced in the constraint set to be reduced to obtain participating variables and participating variable order relationships of each constraint to be reduced. The constraint set reduction method for power system optimization problem according to claim 3 is characterized in that the step of mathematically transforming each to-be-reduced constraint in the to-be-reduced constraint set to obtain the participating variables and the order relationship of the participating variables of each to-be-reduced constraint specifically comprises: Each to-be-reduced constraint in the to-be-reduced constraint set is mathematically transformed to obtain an order constraint, wherein the order constraint is an inequality constraint and the order constraint includes participating variables and an order relationship of the participating variables. The constraint set reduction method for power system optimization problem according to claim 1 is characterized in that The characteristic is that the step of performing node topological sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph specifically includes: Initialize the topological sorted list; Using a breadth/depth first search algorithm to traverse each node in the directed sequence graph, inserting the node with the smallest in-degree in the directed sequence graph into the topological sorting list; Based on the node inserted in the topological sorting list, the inserted node and the edge linked to it are deleted from the directed sequence graph, and the in-degree of each node in the directed sequence graph is updated; Based on the updated in-degrees of the remaining nodes in the directed order graph, the step of inserting the node with the smallest in-degree in the directed order graph into the topological sorting list is re-executed until all the nodes in the directed order graph are inserted into the topological sorting list in sequence, thereby obtaining a node topological sorting result. The constraint set reduction method for the power system optimization problem according to claim 1 is characterized in that, according to the node topological sorting result, each node in the directed ordered graph is traversed and redundant edge elimination processing is performed, and the step of reducing the constraint set to be reduced according to the redundant edge elimination processing result specifically includes: Traversing each node in the directed order graph according to the node topological sorting result and performing redundant edge elimination processing to obtain a transitive reduction graph; Comparing the transitive reduction graph with the directed order graph to determine the reduced redundant edges; The corresponding to-be-reduced constraints in the to-be-reduced constraint set are reduced according to the reduced redundant edges. The constraint set reduction method for the power system optimization problem according to claim 6 is characterized in that the steps of traversing each node in the directed ordered graph and performing redundant edge elimination processing according to the node topological sorting result to obtain the transfer reduction graph specifically include: Traversing each node in the directed sequence graph in turn according to the node topological sorting result, and determining the edges connecting two nodes in the directed sequence graph; According to the node topological sorting result, traverse each edge e=(u,v) in the directed sequence graph in turn, where e represents an edge, u represents a departure node, and v represents an arrival node, and determine whether there are other edges in the directed sequence graph that can go from the departure node u to the arrival node v except the edge e; If it is determined that there are other edges in the directed sequence graph except edge e that can go from the starting node u to When the node v is reached, the edge e is deleted from the directed sequence graph to obtain a transitive reduction graph. The constraint set reduction method for power system optimization problem according to claim 6 is characterized in that the step of comparing the transitive reduction graph with the directed order graph to determine the step of reducing redundant edges specifically comprises: The transitive reduction graph is compared with the directed order graph, and edges that exist in the directed order graph but do not exist in the transitive reduction graph are screened out as reduced redundant edges. The constraint set reduction method for power system optimization problem according to claim 6 is characterized in that the step of reducing the corresponding to-be-reduced constraints in the constraint set to be reduced according to the reduced redundant edges specifically comprises: Obtaining nodes on both sides of the reduced redundant edge; Based on the mapping relationship between nodes and participating variables, the corresponding participating variables and their corresponding to-be-reduced constraints are matched in the to-be-reduced constraint set through the nodes on both sides of the reduced redundant edge; The matched constraints to be reduced are deleted from the set of constraints to be reduced. A constraint set reduction system for power system optimization problems, characterized by comprising: A reduction constraint acquisition module is used to determine multiple constraints to be reduced based on a preset optimization problem of the power system and to construct a set of constraints to be reduced; A graph construction module is used to take each participating variable of the constraint to be reduced as a node, and connect the nodes according to the order relationship of the participating variables to construct a directed order graph; A node topology sorting module is used to perform node topology sorting on all nodes in the directed sequence graph according to the in-degree size of each node in the directed sequence graph; The constraint reduction module is used to traverse each node in the directed order graph according to the node topology sorting result and perform redundant edge elimination processing, and perform constraint reduction on the constraint set to be reduced according to the redundant edge elimination processing result. An electronic device, characterized in that it comprises a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory communicate with each other via the communication bus; Memory, used to store computer programs; A processor, for executing a program stored in a memory, to implement any one of claims 1 to 9 The method steps are described. A computer-readable storage medium, characterized in that a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, the method steps described in any one of claims 1 to 9 are implemented.