JP7834580B2 - Optimization device, optimization method, and program - Google Patents

Description

Embodiments of the present invention relate to an optimization apparatus, an optimization method, and a program.

In recent years, numerous renewable energy generators such as solar and wind power plants, as well as battery storage systems, have been introduced into power grids (hereinafter simply referred to as "the grid"). These are called distributed power sources, and efficient operation is required. Individual distributed power sources have many limitations compared to existing large-scale generators (such as thermal power plants), such as fluctuations in power generation capacity due to weather conditions and operational constraints due to charging and discharging capacity. Therefore, instead of operating these distributed power sources individually, the concept of a virtual power plant (VPP) exists, which integrates and operates many of them together.

When performing optimization calculations for a virtual power plant utilizing multiple distributed power sources, considering constraints such as the active power flow and voltage of the power grid, it is necessary to perform an Optimal Power Flow (OPF) calculation. OPF is a so-called nonconvex nonlinear programming problem, and it is known that, when the problem is large-scale, it requires significantly more computation time compared to convex programming problems such as linear programming problems. Furthermore, if discrete variables such as the start/stop status of generators and the use of distributed power sources are included, it becomes a combinatorial optimization problem, requiring the repeated solving of relaxation problems using methods such as the branch-and-bound method, raising concerns that an optimal solution may not be obtainable within a practical computation time.

In recent years, devices called Ising machines have been developed that can solve combinatorial optimization problems at high speed. To solve a problem with an Ising machine, it is necessary to transform the optimization problem into a form (Quadratic Unconstrained Binary Optimization: QUBO) where there are no constraints, all variables are binary, and the expression is quadratic or less. For example, in conventional techniques, a method has been proposed for determining the system configuration that minimizes power loss in a power distribution network, by representing the connection state using sectionalizing switches as discrete variables and transforming it into a QUBO.

Patent No. 6736787

Alexander Fix, Aritanan Gruber, Endre Boros, Ramin Zabih, “A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields”, IEEE Trans. Pattern Analysis and Machine Intelligence Vol.37 pp.1387-1395 (2015) Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, Martin Szummer, “Optimizing Binary MRFs via Extended Roof Duality”, Technical Report MSR-TR-2007-46 (2007)

While the conventional technology described above allows for optimization calculations targeting the distribution network, it cannot perform optimal power flow calculations for the entire power system, including systems with higher voltages than the distribution network.

Therefore, the problem that this invention aims to solve is to provide an optimization device, an optimization method, and a program that can solve mathematical optimization problems related to the entire power system using an Ising machine.

The optimization apparatus of this embodiment comprises: a problem generation unit that generates a mathematical optimization problem related to cost based on cost information; a variable transformation unit that converts all variables of the mathematical optimization problem into binary variables; a problem transformation unit that transforms the mathematical optimization problem into an unconstrained binary optimization problem; a higher-order term transformation unit that repeatedly performs a process to transform the binary optimization problem into a QUBO-type problem by introducing a new variable into the sum of terms with positive coefficients and a common variable among terms of degree two or three or higher, thereby converting it into a polynomial including terms with negative coefficients, and then transforming it into a quadratic equation by introducing a new variable into terms with negative coefficients and degree three or higher; and an approximate solution calculation unit that solves the QUBO-type problem using an Ising machine.

Figure 1 is a diagram showing the overall configuration of the optimization device 1 according to the first embodiment. Figure 2 is a flowchart showing the operation of the optimization device 1 in the first embodiment. Figure 3 shows a detailed algorithm for S4 in Figure 2. Figure 4 illustrates the effect of suppressing the occurrence of additional variables. Figure 5 shows the overall configuration of the optimization device 1 according to the second embodiment. Figure 6 is a flowchart showing the operation of the optimization device 1 in the second embodiment. Figure 7 shows the overall configuration of the optimization device 1 according to the third embodiment. Figure 8 is a flowchart showing the operation of the optimization device 1 in the third embodiment. Figure 9 shows the overall configuration of the optimization device 1 according to the fourth embodiment. Figure 10 is a flowchart showing the operation of the optimization device 1 in the fourth embodiment. Figure 11 shows the overall configuration of the optimization device 1 according to the fifth embodiment. Figure 12 is a flowchart showing the operation of the optimization device 1 in the fifth embodiment. Figure 13 shows the overall configuration of the optimization device 1 according to the sixth embodiment. Figure 14 is a flowchart showing the operation of the optimization device 1 in the sixth embodiment.

The following describes embodiments of the optimization apparatus, optimization method, and program of the present invention (Embodiments 1 to 6) with reference to the drawings. The outlines of the embodiments are as follows: For the power system, the OPF includes continuous variables, and when this is expressed using discrete variables and transformed into an unconstrained problem, it becomes a quartic equation; therefore, it is transformed into a QUBO type equation. Furthermore, since the number of variables that can be handled by the Ising machine is finite, the number of variables is reduced to decrease the scale of the optimization problem. Moreover, since there is no guarantee that a feasible solution will be obtained from calculations using the Ising machine, the solution obtained by the Ising machine is corrected. The following describes each embodiment. Note that in the second embodiment and subsequent embodiments, explanations of matters similar to those in the previous embodiments will be omitted as appropriate.

(First embodiment)
(composition)
Figure 1 shows the overall configuration of the optimization device 1 according to the first embodiment. In Figure 1, the arrows indicate the main flow of information, and information may also flow in areas without arrows.

The optimization device 1 comprises an Ising machine 11, a processing unit 12, a storage unit 13, a system information receiving unit 14, an input unit 15, and an output unit 16. The operation instruction unit 2 is connected to the optimization device 1 and the power system 3.

The Ising machine 11 can be implemented, for example, by a quantum annealing device or a simulated annealing device. However, the Ising machine 11 is not limited to these and may be other devices or algorithms for solving the QUBO problem. Furthermore, the Ising machine 11 may be implemented as a separate device from the processing unit 12 and connected to the processing unit 12, or it may be implemented as the same device as the processing unit 12.

The processing unit 12 is, for example, a computer including one or more processors. The storage unit 13 is, for example, RAM (Random Access Memory), ROM (Read Only Memory), flash memory (such as SSD (Solid State Drive)), HDD (Hard Disk Drive), etc. The storage unit 13 may be implemented as a separate device from the processing unit 12 and connected to it, or it may be implemented as the same device as the processing unit 12, for example, as main memory or cache memory.

The system information receiving unit 14 is connected to the processing unit 12 and the power system 3. The input unit 15 is connected to the processing unit 12 and includes some or all of the following: various keys, buttons, dial switches, a mouse, a touch panel, etc. The input unit 15 may also be a connection unit electrically connected to an external device.

The output unit 16 is connected to the processing unit 12 and may be a connection unit that electrically connects to an external device, or it may be an LCD (Liquid Crystal Display) or an organic EL (Electro-luminescence) display device, etc.

The processing unit 12 includes a problem generation unit 121, a variable transformation unit 122, a problem transformation unit 123, a higher-order term transformation unit 124, an approximate solution calculation unit 125, a control unit 126, and a data management unit 127. Each functional unit in the processing unit 12 is implemented, for example, by a processor such as a CPU (Central Processing Unit) executing a program (software). Furthermore, some or all of these functional units may be implemented by hardware (including circuitry) such as LSI (Large Scale Integration), ASIC (Application Specific Integrated Circuit), FPGA (Field-Programmable Gate Array), or GPU (Graphics Processing Unit), or by the cooperation of software and hardware. The control unit 126 is connected to the operation instruction unit 2.

The memory unit 13 stores cost information 131, system information 132, mathematical optimization problem 133, binary variable problem 134, unconstrained binary variable problem 135, QUBO problem 136, and approximate solution 137.

Cost information 131 stores constant values used when generating the objective function of the optimization problem, such as the cost incurred during power supply startup, the cost per unit output of the power supply, and the amount of electricity bought and sold in the electricity market. Here, "power supply" refers to thermal power plants, nuclear power plants, hydroelectric power plants, geothermal power plants, solar power plants, wind power plants, and storage batteries. Cost information 131 is input via the input unit 15 and the data management unit 127 and used in the problem generation unit 121 when creating the mathematical optimization problem 133.

The system information 132 stores information such as the open/closed status of switches, load, impedance, capacitance to ground, and tap ratio of transmission lines and transformers, upper and lower voltage limits of busbars on the system, information on power sources present on each busbar, upper and lower limits of active power output for each power source, upper and lower limits of reactive power output for each busbar, and upper and lower limits of active power flow for transmission lines and transformers. The system information 132 may be stored via the input unit 15 and data management unit 127, or via the system information receiving unit 14, and is used in the problem generation unit 121 when creating the mathematical optimization problem 133.

The binary variable problem 134 is created and saved in the variable transformation unit 122. The unconstrained binary variable problem 135 is created and saved in the problem transformation unit 123. The QUBO problem 136 is created and saved in the higher-order term transformation unit 124. The approximate solution 137 is calculated and saved by running the Ising machine 11 in the approximate solution calculation unit 125.

(effect)
The basic operation of the optimization device 1 having the above configuration will now be explained. Figure 2 is a flowchart showing the operation of the optimization device 1 in the first embodiment. In S1, the problem generation unit 121 formulates the optimal power flow calculation as a mathematical optimization problem 133. An example of the mathematical optimization problem 133 is shown below. Here, multiple power sources with different operating costs are connected to each busbar, and we consider an example of an optimal power flow calculation problem that determines the starting and stopping of power sources and their output.

Equation (1) is an example where the objective function is to minimize the costs incurred in operating the power supply. Here, α _m,n are binary variables representing the start/stop state of the nth power supply on bus m (start is "1", stop is "0"). p ^G _m,n are continuous variables representing the output of the nth power supply on bus m. _{C m,n} are constants representing the costs that are always incurred when the nth power supply on bus m is started, and D _m,n are constants representing the costs incurred for the unit output of the nth power supply on bus m, which are read from cost information 131. "G" in m ∈ G is the set of buses where power supplies exist, and "D _m " in n ∈ D _m is the set of power supplies present on bus m, which are read from system information 132.

Equations (2) and (3) are examples of constraints on the supply and demand balance of active and reactive power. ^{P L} _m is a constant representing the active power load of bus m, and Q ^L _m is a constant representing the reactive power load of bus m, both read from system information 132. ^{v Re} _m is a continuous variable representing the real part of the complex voltage (voltage expressed as a complex function) of bus m, and v ^Im _m is a continuous variable representing the imaginary part of the complex voltage of bus m. _{G m,k} are constants representing the mk elements of the conductance component of the admittance matrix, and B _m,k are constants representing the mk elements of the susceptance component of the admittance matrix, both of which can be calculated from the impedance, capacitance to ground, and tap ratio stored in system information 132. ^{q G} _m is a continuous variable representing the reactive power output of bus m. Note that, for simplicity, the reactive power output is abbreviated here without individual variables for each power source, but variables may be provided for each power source.

Equation (4) is a constraint on the active power flow. ^{P min} _l and P ^max _l are the lower and upper limits of the active power flow for branch l, respectively, and are read from the system information 132. L is the set of branches.

Equation (5) is a constraint condition regarding the upper and lower limits of the voltage. ^{V min} _m and V ^max _m are the lower and upper limits of the voltage at busbar m, respectively, and are read from system information 132.

Equation (6) is a constraint condition regarding the upper and lower limits of the active power output of the power supply. ^{P Gmin} _m,n and P ^Gmax _m,n are the lower and upper limits of the active power output of the nth power supply on busbar m, respectively, and are read from system information 132.

Equation (7) is a constraint condition regarding the upper and lower limits of the reactive power output of each busbar. ^{Q Gmin} _m and Q ^Gmax _m are the lower and upper limits of the reactive power output of busbar m, respectively, and are read from system information 132.

The above formulation is just one example; for instance, the costs associated with starting and stopping the generator could be added to the objective function. Alternatively, the objective function could be one that minimizes transmission losses. Furthermore, the problem could be defined as an optimization problem spanning multiple time points, taking into account constraints such as continuous operating time. The information from this formulation is stored in the memory unit 13 as a mathematical optimization problem 133.

In S2, the variable transformation unit 122 converts all variables of the optimal power flow calculation into binary variables. Since the Ising machine 11 generally cannot handle continuous variables, for example, the continuous variable p ^G _m,n is expressed as equation (8) as a linear combination of J ^pg _m,n binary variables x ^pg _m,n,j and weights w ^pg _m,n,j . The expression in the form of equation (8) is called a pseudo-Boolean function. The weights are expressed, for example, in binary. Other continuous variables are similarly converted into binary variables. The required number of ^{J pg} _m,n is calculated from the upper and lower limits of the variables. The converted optimization problem is stored in the memory unit 13 as a binary variable problem 134.

In S3, the problem is transformed into an unconstrained binary optimization problem in the problem transformation section 123. For equations (2) and (3), the left-hand side is squared, multiplied by a predetermined weight, and added to the objective function. For equations (4) and (5), a new variable called a slack variable is introduced to transform them into an equality constraint, and then the same process is performed. For example, the upper limit constraint on active power flow can be transformed as follows by introducing a slack variable s.

Equations (6) and (7) are automatically considered when calculating the weights of the pseudo-Boolean function, provided that the upper and lower bounds are satisfied. The result of the above transformation is saved in the memory unit 13 as the unconstrained binary variable problem 135.

In S4, the higher-order term transformation unit 124 transforms terms of degree 3 or higher into terms of degree 2. S4 uses the method described in Non-Patent Literature 1, which reduces the degree by introducing a new variable to terms that have a common variable. Figure 3 shows a detailed algorithm of S4 in Figure 2. S41 is repeated for all _{x i} ∈ {x ₁ , x ₂ , ...}. x _i represents each variable of the optimization problem. In S41, terms of degree 3 or higher that include the variable x _i and have a positive coefficient (>0) are transformed by equation (10). Here, "H" on the right side of H ∈ H is the set of terms of degree 3 or higher that include x _i and have a positive coefficient (>0), α _H is the coefficient of term H, and y is a newly introduced binary variable (0, 1). As shown in the second term on the right side of equation (10), the degree of terms with a positive coefficient (>0) is reduced. However, as shown in the third term on the right side, terms with a negative coefficient (<0) and the same degree appear.

In S42, terms of degree 3 or higher with negative coefficients (<0) are transformed as follows. In other words, an additional variable y is introduced for each term of degree 3 or higher with negative coefficients (<0).

As a result of processing in S4, the optimization problem to be solved becomes QUBO problem 136, which is then stored in the memory unit 13.

In S5, the approximate solution calculation unit 125 transmits the QUBO problem 136 from the storage unit 13 to the Ising machine 11. The approximate solution calculation unit 125 receives the calculation result from the Ising machine 11 and stores it in the approximate solution 137 in the storage unit 13.

In S6, the control unit 126 reads the approximate solution 137 from the storage unit 13, transmits control signals related to power supply startup/shutdown and output to the operation instruction unit 2, and the operation instruction unit 2 operates the power system 3.

The processes S1 to S5 are executed repeatedly, for example, at 5-second intervals. Note that the above processes do not necessarily need to be executed at the same interval each time; for example, S1 to S4 could be executed at intervals longer than 5 seconds to create the QUBO problem 136, and only S5 and S6 could be executed at 5-second intervals. In this case, if there is a change in the cost information 131, the corresponding part of the QUBO problem 136 is rewritten in S5.

(effect)
Thus, according to the first embodiment, mathematical optimization problems concerning the entire power system can be solved using the Ising machine 11. In other words, problems including constraints expressed as quadratic equations can be solved with the Ising machine 11. For example, in the process in S4, the same higher-order terms appear many times during the transformation process, reducing the number of terms and suppressing the generation of additional variables.

Here, Figure 4 illustrates the effect of suppressing the generation of additional variables. The penalty terms corresponding to the constraints on supply and demand balance and the constraints on active power flow frequently consist of the product of quadratic voltage terms. Note that the penalty terms can be expressed, for example, by squaring the left-hand side of an equality constraint like in equation (9), multiplying it by a weight, and then adding them together.

Furthermore, since voltage is a continuous variable, it is represented using a pseudo-Boolean function in Figure 4. If we assume that each variable is represented by two binary variables (0, 1) for simplicity, the equation can be expanded as shown in Figure 4. Here, we also use the fact that the squared term of a binary variable can be transformed into a first-power term (because ^1/2 = 1 ^{and 0/2} = 0). For example, consider the situation when processing v ^Re ₁₁ in S41. The quartic term v ^Re ₁₁ v ^Re ₁₂ v ^Re ₂₁ v ^Im ₂₁ is decomposed into a cubic term with a positive coefficient, +v ^Re ₁₂ v ^Re ₂₁ v ^Im ₂₁ , and a quartic term with a negative coefficient, -yv ^Re ₁₂ v ^Re ₂₁ v ^Im ₂₁ (where y is a new variable). For -yv ^Re ₁₂ v ^Re ₂₁ v ^Im ₂₁ , we will introduce another new variable in S42 and transform it into a quadratic term. Here, the positive cubic term +v ^Re ₁₂ v ^Re ₂₁ v ^Im ₂₁ has the same form as another term, as shown by the box in the figure, and by combining them, the number of positive higher-order terms decreases. This reduces the generation of negative higher-order terms when processing the next variable, thus reducing the number of additional variables. In OPF, the formulation is such that the above reduction of positive higher-order terms occurs in many parts, so a large reduction in the number of variables can be expected.

(Second embodiment)
Next, a second embodiment will be described.

(composition)
Figure 5 shows the overall configuration of the optimization device 1 according to the second embodiment. The second embodiment is characterized in that a problem size reduction unit 128 is added to the processing unit 12 of the first embodiment (Figure 1), and a reduction problem 138 is added to the storage unit 13.

(effect)
Figure 6 is a flowchart showing the operation of the optimization device 1 in the second embodiment. S7 is added before S5 in the first embodiment (Figure 2). In S7, the problem size is reduced based on graph theory as a preprocessing step. Specifically, for example, Quadratic pseudo-Boolean Optimization (QPBO) is used, which applies graph theory to a quadratic pseudo-Boolean function representation to convert it into a network flow model and partially obtains the global optimal solution by solving the maximum flow problem. In other words, QPBO can obtain solutions for some of the multiple variables. More specifically, this process can be realized by implementing the algorithm in Non-Patent Document 2.

The problem obtained by fixing the variables that were considered part of the global optimal solution in QPBO as constants is saved in the storage unit 13 as a reduced problem 138. In S5, the reduced problem 138 is transmitted to the Ising machine 11. Note that the method used in S7 is not limited to QPBO. Alternatively, S7 and S5 may be executed repeatedly to calculate the solution. Here, the detailed algorithm of S4 is the same as in Figure 3, but in S41, the equation (10) is used to transform the equation for terms of order 2 or higher that include the variable _{x_i} and have a positive coefficient (>0). According to Non-Patent Literature 1, terms of order 2 or higher with a positive coefficient (>0) are called non-inferior modular terms, and the fewer non-inferior modular terms there are, the more variables can be fixed as part of the global optimal solution in QPBO. For example, if equation (10) is applied to five quadratic terms with a common variable and a positive coefficient (>0), the number of quadratic terms with a positive coefficient (>0) is reduced to one (the first term on the right side). In addition, in the first embodiment as well, the operation may be to perform the equation transformation by equation (10) on terms of degree two or higher with positive coefficients (>0).

(effect)
In addition to the effects of the first embodiment, while there is a limit to the number of variables that can be handled by the Ising machine 11, reducing the scale of the optimization problem in S7 makes it possible to run larger-scale problems on the Ising machine 11.

(Third embodiment)
Next, a third embodiment will be described.

(composition)
Figure 7 shows the overall configuration of the optimization device 1 of the third embodiment. The third embodiment is characterized by the addition of an optimization solver 17 to the configuration of the first embodiment (Figure 1). The optimization solver 17 is a device or software capable of solving mathematical optimization problems 133. The optimization solver 17 may be implemented in the same device as the processing unit 12, or it may be implemented as a separate computer from the processing unit 12. Furthermore, the optimization solver 17 can be realized as software that implements, for example, the prim-dual interior-point method or Newton's method. In addition, the solution correction unit 129 is added to the processing unit 12 of the first embodiment (Figure 1), and the corrected solution 139 is added to the storage unit 13.

(effect)
Figure 8 is a flowchart showing the operation of the optimization device 1 in the third embodiment. S8 is added before S6 in the first embodiment (Figure 2). Due to its principle of operation, the Ising machine 11 is not guaranteed to obtain a feasible solution, so the solution correction unit 129 corrects the solution to make it a feasible solution. Specifically, binary variables such as power supply startup and shutdown are fixed in the solution of S5, and an OPF is performed on only the continuous variables.

In S8, each busbar of the system to be solved is equipped with a regulating generator whose active power output has a lower limit of -∞ and an upper limit of +∞, and whose cost becomes significantly higher than other power sources when the output value is anything other than zero. The active power output of the regulating generator is added to the continuous variable. If the solution in S5 is not feasible, a feasible solution is obtained by changing the output of the regulating generator. The change in the output of the regulating generator is allocated to other power sources in the same node. Specifically, if the output of the regulating generator is positive, the output of other power sources is increased in order of decreasing cost by the amount of the regulating generator's output, and power sources that are stopped are started as needed. If the output of the regulating generator is negative, the output of other power sources is decreased in order of increasing cost by the amount of the regulating generator's output, and power sources that are started are stopped as needed. The corrected solution is stored in the storage unit 13 as the corrected solution 139. In S6, the corrected solution 139 is read from the storage unit 13, and control signals regarding the starting/stopping of power sources and their outputs are transmitted to the operation instruction unit 2, which then operates the power system 3.

(effect)
In addition to the effects of the first embodiment, the Ising machine 11 is not normally guaranteed to obtain a feasible solution, but in S8 the solution can be corrected to make it feasible.

(Fourth embodiment)
Next, a fourth embodiment will be described.

(composition)
Figure 9 shows the overall configuration of the optimization device 1 according to the fourth embodiment. The fourth embodiment is characterized in that an iterative solution execution unit 130 is added to the processing unit 12 of the third embodiment (Figure 7), and an iterative solution 140 is added to the storage unit 13.

(effect)
Figure 10 is a flowchart showing the operation of the optimization device 1 in the fourth embodiment. S9 is added before S6 in the third embodiment (Figure 8). Although the solution obtained in S6 is feasible, it is not guaranteed to be the exact optimal solution. In S9, the solution from S6 is used as a provisional solution, and an iterative solution method such as the branch and bound method is executed to search for a solution with low cost (operational cost).

(effect)
This approach may yield a less costly solution than the third embodiment. Furthermore, if it is possible to perform iterative calculations from a provisional solution that is closer to the global optimal solution than conventional iterative methods, the iterative method can be expected to converge faster than before.

Note that in Figure 10, after S5, S9 may be performed without performing S8.

(Fifth Embodiment)
Next, a fifth embodiment will be described.

(composition)
Figure 11 shows the overall configuration of the optimization device 1 according to the fifth embodiment. The fifth embodiment is characterized in that a solution correction unit 129 is added to the processing unit 12 of the second embodiment (Figure 5), and a corrected solution 139 is added to the storage unit 13.

(effect)
Figure 12 is a flowchart showing the operation of the optimization device 1 in the fifth embodiment. S8 is added before S6 in the second embodiment (Figure 6). The operation of S8 is the same as in the third embodiment (Figure 8).

(effect)
In addition to the effects of the second embodiment, it also has the effect of correcting the solution to make it feasible.

(Sixth embodiment)
Next, a sixth embodiment will be described.

(composition)
Figure 13 shows the overall configuration of the optimization device 1 according to the sixth embodiment. The sixth embodiment is characterized in that an iterative solution execution unit 130 is added to the processing unit 12 of the fifth embodiment (Figure 11), and an iterative solution 140 is added to the storage unit 13.

(effect)
Figure 14 is a flowchart showing the operation of the optimization device 1 in the sixth embodiment. S9 is added before S6 in the fifth embodiment (Figure 12). The operation of S9 is the same as in the fourth embodiment (Figure 10).

(effect)
In addition to the effects of the fifth embodiment, a solution with lower costs (operating costs) than the fifth embodiment can be obtained.

The program executed by the optimization device 1 of this embodiment is provided as an installable or executable file recorded on a computer-readable recording medium such as a CD (Compact Disc)-ROM, flexible disk (FD), CD-R, or DVD (Digital Versatile Disk).

Furthermore, the program may be configured to be stored on a computer connected to a network such as the Internet and provided by downloading it via the network. Alternatively, the program may be provided or distributed via a network such as the Internet. Furthermore, the program may be pre-installed and provided in ROM or similar media.

The program in question is structured as a module containing the functional configurations described above. In actual hardware, the CPU reads the program from the storage medium and executes it, loading each functional configuration into main memory and generating it there.

While several embodiments of the present invention have been described, these embodiments are presented as examples only and are not intended to limit the scope of the invention. These novel embodiments can be implemented in various other forms, and various omissions, substitutions, and modifications are possible without departing from the spirit of the invention. These embodiments and their variations are included within the scope and spirit of the invention, as well as within the scope of the invention and its equivalents as described in the claims.

For example, the above-described embodiments may be implemented in combination.

Furthermore, when generating mathematical optimization problems, additional data such as weather data may be used.

1…Optimization device, 2…Operation instruction unit, 3…Power system, 11…Ising machine, 12…Processing unit, 13…Storage unit, 14…System information receiving unit, 15…Input unit, 16…Output unit, 17…Optimization solver, 121…Problem generation unit, 122…Variable transformation unit, 123…Problem transformation unit, 124…Higher-order term transformation unit, 125…Approximate solution calculation unit, 126…Control unit, 127…Data management unit, 128…Problem size reduction unit, 129…Solution correction unit, 130…Iterative solution, 140 method execution unit, 131…Cost information, 132…System information, 133…Mathematical optimization problem, 134…Binary variable problem, 135…Unconstrained binary variable problem, 136…QUBO problem, 137…Approximate solution, 138…Reduction problem, 139…Corrected solution, 140…Iterative solution

Claims (8)

A problem generation unit that generates a mathematical optimization problem related to costs based on cost information regarding the costs incurred in power supply operation ,
A variable transformation unit that transforms all variables in the aforementioned mathematical optimization problem into binary variables,
A problem transformation unit that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients that are quadratic or quadratic or higher in order of degree 2 or higher and share a common variable, thereby transforming them into a polynomial that includes terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients that are quadratic or higher in order of degree 3 or higher, thereby transforming them into quadratic expressions. This process converts the problem into a QUBO (Quadratic Unconstrained Binary Optimization) format problem.
An optimization apparatus comprising: an approximate solution calculation unit that solves the QUBO format problem using an Ising machine; and A system information receiving unit that collects system information, which is information about the power system,
A problem generation unit that generates a mathematical optimization problem relating to costs based on the aforementioned system information and cost information relating to the power system,
A variable transformation unit that transforms all variables in the aforementioned mathematical optimization problem into binary variables,
A problem transformation unit that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients and a common variable among terms of degree 2 or 3 or higher, thereby transforming them into a polynomial containing terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients and a degree 3 or higher, thereby transforming them into quadratic expressions and converting them into a QUBO-type problem.
An optimization apparatus comprising: an approximate solution calculation unit that solves the QUBO format problem using an Ising machine; and The optimization apparatus according to claim 1 or claim 2, further comprising a solution correction unit that performs a process of fixing the binary variables with the solutions obtained by an Ising machine and performing an optimal power flow calculation (OPF) for the continuous variables with respect to the approximate solution calculated by the approximate solution calculation unit. The optimization apparatus according to claim 3 , further comprising an iterative solution execution unit that executes an iterative solution method using the solution calculated by the solution correction unit as a provisional solution. An optimization method performed by a computer,
A problem generation step that generates a mathematical optimization problem related to costs based on cost information regarding the costs incurred in power supply operation ,
A variable transformation step in which all variables of the aforementioned mathematical optimization problem are transformed into binary variables,
A problem transformation step that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients and a common variable among terms of degree 2 or 3 or higher, thereby transforming them into a polynomial containing terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients and a degree 3 or higher, thereby transforming them into quadratic expressions and converting them into a QUBO-type problem.
An optimization method comprising: a step of calculating an approximate solution to the QUBO-format problem using an Ising machine. Computers,
A problem generation unit that generates a mathematical optimization problem related to costs based on cost information regarding the costs incurred in power supply operation ,
A variable transformation unit that transforms all variables in the aforementioned mathematical optimization problem into binary variables,
A problem transformation unit that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients that are quadratic or quadratic or higher in order of degree 2 or higher and share a common variable, thereby transforming them into a polynomial that includes terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients that are quadratic or higher in order of degree 3 or higher, thereby transforming them into quadratic expressions. This process converts the problem into a QUBO (Quadratic Unconstrained Binary Optimization) format problem.
An approximate solution calculation unit that uses an Ising machine to solve the aforementioned QUBO format problem, and a program for causing it to function as such. An optimization method performed by a computer,
A system information receiving step that collects system information, which is information about the power system,
A problem generation step of generating a mathematical optimization problem relating to costs based on the aforementioned system information and cost information relating to the power system,
A variable transformation step in which all variables of the aforementioned mathematical optimization problem are transformed into binary variables,
A problem transformation step that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients and a common variable among terms of degree 2 or 3 or higher, thereby transforming them into a polynomial containing terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients and a degree 3 or higher, thereby transforming them into quadratic expressions and converting them into a QUBO-type problem.
An optimization method comprising: a step of calculating an approximate solution to the QUBO-format problem using an Ising machine. Computers,
A system information receiving unit that collects system information, which is information about the power system,
A problem generation unit that generates a mathematical optimization problem relating to costs based on the aforementioned system information and cost information relating to the power system,
A variable transformation unit that transforms all variables in the aforementioned mathematical optimization problem into binary variables,
A problem transformation unit that transforms the aforementioned mathematical optimization problem into an unconstrained binary optimization problem,
Regarding the aforementioned binary optimization problem, the process involves repeatedly introducing a new variable into the sum of terms with positive coefficients and a common variable among terms of degree 2 or 3 or higher, thereby transforming them into a polynomial containing terms with negative coefficients. Then, the process involves introducing a new variable into terms with negative coefficients and a degree 3 or higher, thereby transforming them into quadratic expressions and converting them into a QUBO-type problem.
An approximate solution calculation unit that uses an Ising machine to solve the aforementioned QUBO format problem, and a program for causing it to function as such.