JP7800517B2 - Optimization device, optimization method, and computer program - Google Patents

Description

The present invention relates to an optimization device, an optimization method, and a computer program.

Optimization devices for solving combinatorial optimization problems have been known for some time (for example, Non-Patent Document 1).

S. Feld, C. Eoch, T. Gabor, C. Seidal, F. Neukart, I. Galter, W. Mauerer and C. Linnhoff-Popien, "A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer," Frontiers in ICT, VOL 6, 2019, [Retrieved July 10, 2023], Internet: <https://www.frontiersin.org/articles/10.3389/fict.2019.00013/full>

However, even with prior art such as that disclosed in Patent Document 1, there was still room for improvement in the technology used by optimization devices to find optimized combinations for combinatorial optimization problems that involve constraints that are difficult to formulate.

The present invention was made to solve the above-mentioned problems, and aims to provide technology in an optimization device that can find optimized combinations even for combinatorial optimization problems that have constraints that are difficult to formulate.

The present invention has been made to solve at least some of the above-mentioned problems, and can be realized in the following forms.

(1) One aspect of the present invention provides an optimization device for solving combinatorial optimization problems that are subject to constraints. The optimization device includes an input unit that receives basic information about basic components of combinations and constraint information about the constraints; a data acquisition unit that acquires data about optimized combinations using the basic information; a correction unit that corrects the basic information using the data about the optimized combinations acquired by the data acquisition unit and the constraint information; and a learning unit that acquires new basic information that has learned the constraints using the basic information corrected by the correction unit. The data acquisition unit acquires new data about the optimized combinations using the new basic information acquired by the learning unit, the correction unit uses the new data about the optimized combinations acquired by the data acquisition unit and the constraint information to correct the new basic information acquired by the learning unit, and the learning unit acquires new basic information that has further learned the constraints using the new basic information corrected by the correction unit.

With this configuration, the correction unit corrects the basic information using the data of the optimized combination and the constraint information acquired by the data acquisition unit. The learning unit uses the basic information corrected by the correction unit to acquire new basic information that has learned the constraints. The data acquisition unit uses the new basic information acquired by the learning unit to acquire new data of the optimized combination. This makes it possible to find optimized combinations even for combinatorial optimization problems that are difficult to formulate and have constraints that are difficult to include as basic information. The correction unit also corrects the new basic information using the new data of the optimized combination and the constraint information acquired by the data acquisition unit, and the learning unit uses the new basic information corrected by the correction unit to acquire new basic information that has further learned the constraints. In this way, by sequentially repeating the acquisition of data of the optimized combination by the data acquisition unit and the acquisition of basic information that has learned the constraints by the learning unit, it is possible to find even more optimized combinations from among combinations that satisfy the constraints. Therefore, it is possible to find optimized combinations for combinatorial optimization problems that have constraints that are difficult to formulate.

(2) In the optimization device of the above aspect, the correction unit may include a condition determination unit that determines whether the optimized combination acquired by the data acquisition unit satisfies the constraint conditions, and an information update unit that updates the basic information when the condition determination unit determines that the optimized combination does not satisfy the constraint conditions. According to this configuration, the correction unit updates the basic information depending on whether the optimized combination acquired by the data acquisition unit satisfies the constraint conditions. The learning unit acquires new basic information that has learned the constraint conditions using the basic information corrected in response to the determination by the condition determination unit, in order for the data acquisition unit to acquire new data for the optimized combination. This makes it possible to determine a more optimized combination from among the combinations that satisfy the constraint conditions.

(3) In the optimization device of the above aspect, the data acquisition unit may calculate an evaluation value of the optimized combination, and the information update unit may update the basic information by changing the evaluation value using a penalty value corresponding to the constraint condition when the condition determination unit determines that the optimized combination does not satisfy the constraint condition. With this configuration, when the condition determination unit determines that the optimized combination does not satisfy the constraint condition, the information update unit changes the evaluation value of the optimized combination using a penalty value corresponding to the constraint condition, thereby ensuring that the constraint information is included in the new basic information. This makes it possible to find a more optimized combination from among the combinations that satisfy the constraint condition.

(4) The optimization device of the above aspect may include an evaluation/determination unit that determines whether a corrected evaluation value, obtained by adding the penalty value to the evaluation value, is equal to or less than a predetermined reference point, and the learning unit may acquire new basic information that has learned the constraint conditions using new basic information updated by the information update unit when the evaluation/determination unit determines that the corrected evaluation value is greater than the reference point. According to this configuration, the learning unit acquires new basic information that has learned the constraint conditions in accordance with a determination of whether the corrected evaluation value, obtained by adding the penalty value to the evaluation value, is equal to or less than a predetermined reference point, and the data acquisition unit acquires new data of optimized combinations using the new basic information. As a result, once data of combinations for which optimization has reached a certain level has been acquired, the optimization device can terminate solving the combinatorial optimization problem, thereby shortening the time required to acquire data of optimized combinations.

(5) In the optimization device of the above embodiment, the learning unit may acquire new basic information in a format of binary variable optimization without quadratic constraints. According to this configuration, the learning unit acquires new basic information in a format of binary variable optimization without quadratic constraints. This makes it possible to use Ising machines such as simulated annealing and quantum annealing to acquire data on optimized combinations.

(6) In the optimization device of the above aspect, the data acquisition unit may acquire data on optimized combinations using a binary variable optimization solver without quadratic constraints. According to this configuration, the data acquisition unit acquires data on optimized combinations using a binary variable optimization solver without quadratic constraints, such as an Ising machine. This reduces the time required to acquire data on optimized combinations.

(7) Another aspect of the present invention provides an optimization method for solving a combinatorial optimization problem that is subject to constraints using an optimization device. This optimization method includes an input process for inputting basic information regarding basic components of a combination and constraint information regarding the constraints; a first data acquisition process for acquiring data of an optimized combination using the basic information; a correction process for correcting the basic information using the data of the optimized combination acquired in the first data acquisition process and the constraint information; a learning process for acquiring new basic information that has learned the constraints using the basic information corrected in the correction process; and a second data acquisition process for acquiring new data of the optimized combination using the new basic information acquired in the learning process. According to this configuration, in the correction process, the basic information is corrected using the data of the optimized combination acquired in the first data acquisition process and the constraint information. In the learning process, new basic information that has learned the constraints is acquired using the basic information corrected in the correction process, and in the second data acquisition process, new data of the optimized combination is acquired using the new basic information that has learned the constraints. This makes it possible to find, for example, an optimized combination from among combinations that satisfy constraint conditions that are difficult to formulate. Furthermore, using the new data and constraint information for the optimized combination acquired in the second data acquisition process, new basic information that further learns the constraint conditions can be acquired in the learning process. In this way, by sequentially repeating the acquisition of data for the optimized combination and the acquisition of basic information that learns the constraint conditions, it is possible to find a further optimized combination from among combinations that satisfy the constraint conditions.

(8) According to yet another aspect of the present invention, a computer program is provided that causes a computer to solve a combinatorial optimization problem that is subject to constraints. The computer program causes the computer to execute the following functions: an input function that inputs basic information regarding basic components of a combination and constraint information regarding the constraints; a first data acquisition function that acquires data of an optimized combination using the basic information; a correction function that corrects the basic information using the data of the optimized combination acquired by the first data acquisition function and the constraint information; a learning function that acquires new basic information that has learned the constraints using the basic information corrected by the correction function; and a second data acquisition function that acquires new data of the optimized combination using the new basic information acquired by the learning function. According to this configuration, the correction function of the computer corrects the basic information using the data of the optimized combination acquired by the first data acquisition function and the constraint information. The learning function uses the basic information corrected by the correction function to acquire new basic information that has learned the constraints, and the second data acquisition function acquires new data of the optimized combination using the new basic information that has learned the constraints. This makes it possible, for example, to find an optimized combination from among combinations that satisfy constraint conditions that are difficult to formulate. Furthermore, using new data and constraint information for the optimized combination obtained by the second data acquisition function, the learning function can acquire new basic information that further learns the constraint conditions. In this way, by sequentially repeating the acquisition of data for the optimized combination and the acquisition of basic information that learns the constraint conditions, it is possible to find an even more optimized combination from among combinations that satisfy the constraint conditions.

The present invention can be realized in various forms, such as a system including an optimization device, a control method for these devices and systems, a computer program for executing the optimization method in these devices and systems, a server device for distributing the computer program, and a non-transitory storage medium on which the computer program is stored.

FIG. 1 is a schematic block diagram of an optimization device according to a first embodiment. 1 is a flowchart outlining an optimization method according to a first embodiment. FIG. 1 is a first diagram illustrating a specific example of a combinatorial optimization problem. FIG. 10 is a second diagram illustrating a specific example of a combinatorial optimization problem. 1 is a specific example of a flowchart of an optimization method according to the first embodiment. 10A and 10B are diagrams illustrating the effects of the optimization method according to the first embodiment. FIG. 2 is a schematic diagram illustrating an optimization method according to the first embodiment.

First Embodiment
FIG. 1 is a schematic block diagram of an optimization device 1 according to a first embodiment. The optimization device 1 according to this embodiment is a device for solving various combinatorial optimization problems, particularly suitable for solving optimization problems with constraints that are difficult to formulate. The optimization device 1 according to this embodiment is configured as a personal computer (PC). The optimization device 1 includes an input unit 10 that accepts input from a user, a storage unit 20, a CPU (Central Processing Unit) 30 that executes various programs, an output unit 40 that outputs information related to the execution results of the programs, and a transmission/reception unit 50 that can transmit and receive various information to and from other devices via wired or wireless connections. While the optimization device 1 according to this embodiment is described as a single personal computer, it may also be configured as a plurality of devices. For example, an input/output terminal including the input unit 10 and the output unit 40 and a calculation device including the storage unit 20 and the CPU 30 may be located in separate locations, and the input/output terminal and the calculation device may be connected via a network.

The input unit 10 receives input of basic information about the basic components of the combinations searched for by the optimization device 1 and constraint information about the constraints imposed on the combinations. In this embodiment, the basic components refer to the elements themselves that are combined in the search for combinations, and the basic information refers to information necessary for the optimization device 1 to obtain combination data. For example, in the electric vehicle travel route problem described below, the basic components are the travel cost between two locations that the electric vehicle must visit, and the basic information includes the number of locations that the electric vehicle must visit and the number of charging stations. The constraint information refers to information about the conditions (constraints) that the combinations searched for must observe. For example, in the electric vehicle travel route problem, the constraint information includes the maximum electric capacity of the battery equipped in the electric vehicle. In this embodiment, the input unit 10 is composed of a keyboard and a mouse. However, the input unit 10 is not limited to this and may also be an interface with an external storage device, such as a USB memory or flash memory, on which the basic information and constraint information are stored. Furthermore, in this embodiment, the input of basic information and constraint information is not limited to being via the input unit 10, but may also be input by receiving this information from another device (not shown) using the transceiver unit 50.

The storage unit 20 stores the basic information and constraint information input by the input unit 10, as well as a computer program for solving combinatorial optimization problems. In this embodiment, the storage unit 20 is a general term for memory devices, and various types of storage devices can be used, such as ROM (Read Only Memory), RAM (Random Access Memory), solid state drives (SSDs), hard disks (HDDs), and flash memory cards.

The CPU 30 executes the functions of various programs by loading programs stored in the ROM of the storage unit 20 into the RAM. The CPU 30 functions as a data acquisition unit 31, a correction unit 32, an evaluation/determination unit 33, and a learning unit 34.

The data acquisition unit 31 acquires data on optimized combinations using basic information. There are two methods for acquiring data on optimized combinations in the data acquisition unit 31: acquiring data using basic information input by the input unit 10, or acquiring data using new basic information acquired through learning in the learning unit 34. In this embodiment, the data acquisition unit 31 calculates an evaluation value for the acquired optimized combination data to evaluate the optimality of the combination. The functions of the data acquisition unit 31 will be described in detail below.

The correction unit 32 corrects the basic information using the data of the optimized combination acquired by the data acquisition unit 31 and the constraint information. The correction unit 32 has a condition determination unit 32a and an information update unit 32b. The condition determination unit 32a determines whether the optimized combination acquired by the data acquisition unit 31 satisfies the constraint conditions included in the constraint information. The information update unit 32b updates the basic information according to the determination result of the condition determination unit 32a. In this embodiment, the information update unit 32b updates the basic information using the evaluation value calculated by the data acquisition unit 31 and the penalty value corresponding to the constraint condition. The function of the correction unit 32 will be described in detail below.

The evaluation and determination unit 33 determines the optimality of the optimized combination acquired by the data acquisition unit 31. In this embodiment, the evaluation and determination unit 33 determines the optimality using the basic information corrected by the correction unit 32. Details of the function of the evaluation and determination unit 33 will be described later.

The learning unit 34 uses the basic information corrected by the correction unit 32 to obtain new basic information that has learned the constraints. In this embodiment, the learning unit 34 obtains new basic information using Bayesian estimation for the basic information corrected by the correction unit 32. Details of the function of the learning unit 34 will be described later.

Figure 2 is a flowchart outlining the optimization method of this embodiment. Figure 2 is a generalized representation of the flowchart of the optimization method of this embodiment. The optimization method illustrated by the flowchart in Figure 2 is applied to combinatorial optimization problems to which constraints are imposed (hereinafter referred to as "constrained optimization problems"). Constrained optimization problems to which the optimization method of this embodiment is applied aim to find an input x that gives the solution z with the best evaluation value y in a situation where constraints that must be satisfied for a solution z for input x are imposed. Furthermore, the constrained optimization problem of this embodiment is characterized by the difficulty of formulating the constraints that must be satisfied for solution z.

In the optimization method for solving a constrained optimization problem of this embodiment, as shown in FIG. 2, first, basic data including basic information and constraint information is input by the input unit 10 (step S1). Next, the data acquisition unit 31 solves the unconstrained optimization problem using the basic information (step S2). As a result, the data acquisition unit 31 derives a solution z for the input x and acquires data for the optimized combination of the input x and solution z. No constraints are imposed on the solution z derived in step S2. After deriving the solution z for the input x, the data acquisition unit 31 calculates a provisional evaluation value a for the solution z for the input x (step S3). Step S1 corresponds to the "input step" in the claims. Step S2 corresponds to the "first data acquisition step" in the claims.

Next, the condition determination unit 32a uses the data for the combination of input x and solution z and the constraint information acquired by the data acquisition unit 31 to determine whether solution z satisfies the constraint conditions (step S4). If the condition determination unit 32a determines that solution z satisfies the constraint conditions (step S4: YES), the process proceeds to step S5. If the condition determination unit 32a determines that solution z does not satisfy the constraint conditions (step S4: NO), the process proceeds to step S6.

In step S5, the condition determination unit 32a sets the provisional evaluation value a as the evaluation value y for input x (step S5). Meanwhile, in step S6, the condition determination unit 32a sets the value (modified evaluation value) obtained by performing an operation using the provisional evaluation value a and the penalty value b corresponding to the constraint condition as the evaluation value y for input x (step S6). Note that the operation using the penalty value b in step S6 may be, for example, an arithmetic operation such as addition or subtraction, but is not limited to these. The change in the magnitude of the evaluation value y due to the operation in step S6 is important in determining the optimality in step S8, which will be described later. Therefore, the operation in step S6 will differ depending on the content of the constrained optimization problem to which the optimization method of this embodiment is applied.

After step S5 or step S6, the information update unit 32b updates the evaluation value y for the input x according to the processing of step S5 or step S6 (step S7). That is, the correction unit 32 changes the evaluation value using the penalty value b corresponding to the constraint, thereby correcting the basic information used in obtaining data for the optimized combination of input x and solution z in the previous step S2 to basic information that takes the constraint into account. Steps S4 to S7 correspond to the "correction process" in the claims.

Next, the evaluation determination unit 33 determines whether the evaluation value y for the input x satisfies a preset criterion (step S8). In step S8, for example, it determines whether the evaluation value y updated in step S7 is equal to or less than a reference value. If the evaluation determination unit 33 determines that the evaluation value y is equal to or less than the reference value (step S8: YES), the current optimization method ends. If the evaluation determination unit 33 determines that the evaluation value y is not equal to or less than the reference value (step S8: NO), the process proceeds to step S9. Note that the method of determination in the evaluation determination unit 33 is not limited to whether it is equal to or less than the reference value. For example, it may be equal to or greater than the reference value, or it may be within a predetermined range.

If it is determined in step S8 that the evaluation value y is not less than the reference value, the relationship between the input x and the evaluation value y is learned using Bayesian estimation (step S9). Specifically, the learning unit 34 uses the evaluation value y updated in step S7 to learn the relationship between the input x and the evaluation value y in Bayesian estimation expressed as y = f(x). This allows the learning unit 34 to acquire new basic information that has learned the constraints, including information about combinations that were not subject to the judgment in steps S3 to S7. Step S9 corresponds to the "learning process" in the claims.

Next, a new input x is determined (step S10). Specifically, the data acquisition unit 31 uses the new basic information acquired in step S9 to determine a new input x that is estimated to be the optimal input. Note that the method for determining the input x in steps S9 and S10 is not limited to Bayesian estimation.

After step S10, the process returns to step S2, where the new basic information acquired in step S9 is used to solve the unconstrained optimization problem (step S2). In the optimization method of this embodiment, by sequentially performing the processes from step S2 through two judgments (steps S4 and S8) to step S10, it is possible to determine the input x that gives the solution z with the best evaluation value y. Step S10 and the step S2 that follows step S10 correspond to the "second data acquisition step" in the claims.

Next, the optimization method of this embodiment will be explained using a specific example. In this embodiment, the constrained optimization problem is to optimize the travel route of an electric vehicle, taking into account the maximum electric capacity of the electric vehicle. The combinatorial optimization problem to which the optimization method of this embodiment is applied, as described below, will be simply referred to as the "electric vehicle travel route problem." The optimization method of this embodiment is executed when the user inputs basic information and constraint information.

Figure 3 is the first diagram illustrating a specific example of a combinatorial optimization problem of this embodiment. Figure 3 is a diagram showing an example of the relationship between points P1 to P10 that an electric vehicle EV must visit and charging stations installed at some of the points P1 to P10 in an electric vehicle travel path problem. In Figure 3, charging stations Sp1 to Sp3 are installed at three of the points P1 to P10 that the electric vehicle EV must visit: P3, P6, and P10. In the electric vehicle travel path problem, the electric vehicle EV visits all 10 points P1 to P10 that it must visit while charging at each of the charging stations Sp1 to Sp3. The locations where each of the charging stations Sp1 to Sp3 is installed are the targets of optimization in the electric vehicle travel path problem of this embodiment. Information regarding the locations where each of the charging stations Sp1 to Sp3 is installed is included in the basic information as an initial setting. Note that Figure 3 only shows the schematic relationship between the 10 points P1 to P10, and does not indicate the distance or direction between each of the points P1 to P10.

Figure 4 is a second diagram illustrating a specific example of a combinatorial optimization problem according to this embodiment. Figure 4 shows information related to the consumption of the battery provided in an electric vehicle. Specifically, it shows the amount of electricity consumed when traveling between two of the points P1 to P10 shown in Figure 3. In Figure 4, the horizontal axis shows the point from which the electric vehicle departs (departure point), and the vertical axis shows the point at which the electric vehicle arrives (arrival point). Figure 4 shows the amount of battery consumption in relation to the departure point and the arrival point as dot density. Specifically, the higher the dot density, the greater the battery consumption. The information shown in Figure 4 is included in the basic information.

The battery consumption of an electric vehicle differs, for example, when the departure point is A and the destination point is B, compared to when the departure point is B and the destination point is A. Referring to Figure 4, if the departure point is P6 and the destination point is P8, battery consumption Cs68 will be close to 5, but if the departure point is P6 and the destination point is P8, battery consumption Cs86 will be around 4. This is because, for example, if there is a downhill slope due to the difference in elevation between the two points, the battery can be charged without discharging. Therefore, between two points, battery consumption may be less than 0.

In this embodiment, the maximum electrical capacity of the battery equipped in an electric vehicle is assumed to be 3, and an amount of electricity equivalent to the battery's electrical capacity of 2 can be charged to the battery at one charging station. In the electric vehicle travel route problem in this embodiment, the charging station is located at the optimal location and a route with the lowest battery consumption (travel cost) is found under the capacity constraint (constraint condition) that the amount of electricity in the battery must not exceed the maximum electrical capacity of 3 and must not fall below 0. In other words, in the electric vehicle travel route problem to which the optimization method of this embodiment is applied, both the location of the charging station and the electric vehicle travel route are optimized while taking into account the capacity constraint of the battery equipped in the electric vehicle.

Figure 5 is a specific example of a flowchart of the optimization method of this embodiment. In the optimization method for the electric vehicle travel path problem, basic data is first input (step S11). In step S11, basic information and constraint information for the electric vehicle travel path problem are input to the optimization device 1 by the input unit 10. As described above, the basic information input in step S11 includes information on the number of locations to be visited by the electric vehicle, the number of charging stations, and the travel costs between the locations to be visited by the electric vehicle shown in Figure 4. As described above, information on the locations where charging stations will be installed is included in the basic information as an initial setting. Hereinafter, for convenience, the locations where charging stations will be installed will be referred to as "charging station location x." Charging station location x corresponds to input x in the general expression of the optimization method described in Figure 2.

Next, the optimal route problem without capacity constraints is solved (step S12). In step S12, the data acquisition unit 31 solves the electric vehicle travel route problem using basic information. As a result, the data acquisition unit 31 acquires the optimal travel route z for the charging station location x as "optimized combination data." In step S12, the electric vehicle travel route problem is solved using basic information including information about the charging station location x, so the amount of electricity in the electric vehicle's battery must not exceed 3, which is the maximum electrical capacity, and must not be greater than 0 when acquiring the optimal travel route z. The optimal travel route z acquired in step S12 corresponds to the solution z in the general expression of the optimization method described in Figure 2.

Next, an evaluation value of the optimal travel route is calculated (step S13). In step S13, the data acquisition unit 31 calculates an evaluation value a of the optimal travel route z at the charging station location x acquired in step S12. The evaluation value a can be substituted with the travel cost calculated when solving the electric vehicle travel route problem in step S12. However, the evaluation value is not limited to this. The evaluation value a corresponds to the provisional evaluation value a in the general expression of the optimization method described in Figure 2.

Next, it is determined whether the optimal travel route satisfies the battery capacity constraint (step S14). In step S14, the condition determination unit 32a determines whether the amount of electricity in the battery of the electric vehicle for the optimal travel route z of the electric vehicle at the charging station position x calculated in step S12 is 3 or less and greater than 0. If the condition determination unit 32a determines that the optimal travel route z satisfies the capacity constraint (step S14: YES), the process proceeds to step S15. If the condition determination unit 32a determines that the optimal travel route z does not satisfy the capacity constraint (step S14: NO), the process proceeds to step S16.

If it is determined in step S14 that the optimal travel route z satisfies the capacity constraint, in step S15, the condition determination unit 32a sets the evaluation value a calculated in step S13 as the travel cost y of the optimal travel route z (step S15). The travel cost y corresponds to the evaluation value y in the general expression of the optimization method described in Figure 2.

On the other hand, if it is determined in step S14 that the optimal travel route z does not satisfy the capacity constraint, the sum of the evaluation value a and the penalty value b is set as the travel cost y of the optimal travel route z (step S16). In step S16, the condition determination unit 32a sets the value obtained by adding the penalty value b corresponding to the capacity constraint to the evaluation value a calculated in step S13 (modified evaluation value) as the travel cost y of the optimal travel route z. In other words, if the optimal travel route does not satisfy the capacity constraint, the travel cost of that optimal travel route is likely to be higher than that of an optimal travel route that satisfies the capacity constraint. Note that in electric vehicle travel route problems, a small travel cost is desirable, so if the capacity constraint is not satisfied, the travel cost is set as the value obtained by adding the penalty value to the evaluation value.

Following step S15 or step S16, the travel cost is updated (step S17). In step S17, the information update unit 32b updates the travel cost y at the charging station position x following the processing in step S15 or step S16, and corrects it to basic information that takes capacity constraints into account.

Next, it is determined whether a movement cost equal to or less than a reference value has been acquired (step S18). In step S18, the evaluation and determination unit 33 determines whether the movement cost updated in step S17 is equal to or less than a preset reference value. If the evaluation and determination unit 33 determines that a movement cost y equal to or less than the reference value has been acquired (step S18: YES), the current optimization method is terminated. If the evaluation and determination unit 33 determines that a movement cost y equal to or less than the reference value has not been acquired (step S18: NO), the process proceeds to step S19.

If it is determined in step S18 that a travel cost y equal to or less than the reference value has not been acquired, the coefficient matrix for Bayesian estimation is estimated (step S19). In step S19, the learning unit 34 estimates the coefficient matrix A of the following equation (1) using Bayesian estimation. As a result, the learning unit 34 acquires new basic information that has learned the capacity constraints. The new basic information acquired by the learning unit 34 also includes information about combinations that were not subject to the determination in steps S13 to S17. In this embodiment, the learning unit 34 can acquire new basic information in the form of quadratic unconstrained binary optimization (QUBO).

Next, a new position x of the charging station is determined (step S20). Specifically, the data acquisition unit 31 determines the new position x of the charging station using the coefficient matrix A estimated in step S19.

After step S20, an optimal route problem without capacity constraints is solved at the new charging station position x determined in step S20 (step S12). In step S12, the data acquisition unit 31 solves the electric vehicle travel route problem at the newly determined charging station position x using the new basic information acquired in step S20. In this embodiment, in the second and subsequent iterations of step S12, optimized combination data is acquired using a binary variable optimization solver without quadratic constraints, such as an Ising machine. As a result, the data acquisition unit 31 acquires new optimized combination data using the new basic information acquired by the learning unit 34 that has learned the capacity constraints.

In this manner, the optimization method of this embodiment repeats steps S12 to S20, and in step S18, the optimal travel route z for which the travel cost y is equal to or less than the reference value is determined as the final optimal travel route z. The determined optimal travel route for the electric vehicle is output using the output unit 40.

Figure 6 is a diagram illustrating the effects of the optimization method of this embodiment. Figure 6 shows the calculation results for the relationship between the travel cost of an electric vehicle and the number of searches for charging station locations, using the optimization method described in Figure 5, when three charging stations are located. The horizontal axis of Figure 6 shows the number of searches for charging station locations (the number of times step S20 was executed), and the vertical axis shows the travel cost of the electric vehicle calculated for each search. Figure 6 also shows the results when a penalty value of 10 is added to the evaluation value if the capacity constraint is violated in the determination made in step S14 (see step S16). As shown in Figure 6, it can be seen that a solution that does not violate the capacity constraint can be found after approximately 50 searches. Furthermore, it can be seen that a solution with a travel cost of 7.69 that does not violate the capacity constraint can be found after approximately 130 searches.

Figure 7 is a schematic diagram illustrating the optimization method of this embodiment. The schematic diagram shown in Figure 7 illustrates a learning process using Bayesian Optimization of Combinatorial Structure (hereinafter referred to as "BOCS"). In the optimization method illustrated in the schematic diagram in Figure 7, the relationship between input x, which is a bit string of binary variables representing combinations, and output z is unknown. In Figure 7, a system in which the relationship between input x and output z is unknown is shown as z = f(x), and this corresponds to the electric vehicle travel route problem described in Figures 3 to 6.

In the optimization method shown in Figure 7, for a system where the relationship between input x and output z is unknown, a data set of output z for a given input x is first obtained (arrow PR1 in Figure 7). In the electric vehicle travel route problem described in Figures 3 to 6, input x corresponds to the location x of the charging station, and output z corresponds to the optimal travel route z for the electric vehicle.

Next, using the acquired data set of input x (location of charging stations) and output z (optimal electric vehicle travel route), the relationship between input x and output z is learned in QUBO (Quadratic Unconstrained Binary Optimization) format (arrow PR2 in Figure 7). When learning the relationship between input x and output z in QUBO format, it is determined whether output z satisfies the constraint. If output z does not satisfy the constraint, the constraint can be learned by updating the relationship between input x and output z using a penalty value corresponding to the constraint. In the electric vehicle travel route problem described in Figures 3 to 6, learning the capacity constraint means that if there is a violation of the capacity constraint related to the electric capacity of the battery equipped in the electric vehicle, the sum of the evaluation value and the penalty value is set as the travel cost of the electric vehicle.

Next, based on the learned relationship, a search is performed for the next input x candidate that provides the optimal output z (arrow PR3 in Figure 7). When searching for the optimal input candidate, simulated annealing (SA) or quantum annealing (QA) can be used because the relationship between input x and output z is learned using the QUBO format. In the electric vehicle routing problem described in Figures 3 to 6, this corresponds to the search for a new charging station location in step S20. In this way, in the constraint condition learning process using BOCS, the search is repeated, with the cycle from arrow PR1 to arrow PR3 counting as one search, and the coefficient matrix A is updated each time a data set of output z for input x is obtained. This makes it possible to find the input x that provides the optimal output z with greater accuracy. Note that in the constraint condition learning process using BOCS, searches are sequentially repeated a predetermined number of times.

According to the optimization device 1 of this embodiment described above, the correction unit 32 corrects the basic information using the optimized combination data and constraint information acquired by the data acquisition unit 31. The learning unit 34 uses the basic information corrected by the correction unit 32 to acquire new basic information that has learned the constraint conditions. The data acquisition unit 31 acquires new data of the optimized combination using the new basic information that has learned the constraint conditions. This makes it possible to find an optimized combination from among combinations that satisfy the constraint conditions, even for a combinatorial optimization problem that is difficult to formulate and has constraint conditions that make it difficult to include information as basic information when acquiring data of the optimized combination. Furthermore, the correction unit 32 corrects the new basic information using the new data of the optimized combination and constraint information acquired by the data acquisition unit 31, and the learning unit 34 uses the new basic information corrected by the correction unit 32 to acquire new basic information that has further learned the constraint conditions. In this way, by sequentially repeating the acquisition of data on optimized combinations by the data acquisition unit 31 and the acquisition of new basic information that has learned the constraints by the learning unit 34, it is possible to find even more optimized combinations from among the combinations that satisfy the constraints. Therefore, it is possible to find optimized combinations for combinatorial optimization problems that are subject to constraints that are difficult to formulate.

Furthermore, according to the optimization device 1 of this embodiment, the correction unit 32 updates the basic information depending on whether the optimized combination acquired by the data acquisition unit 31 satisfies the constraint conditions, and the learning unit 34 acquires new basic information that has learned the constraint conditions in order to acquire new data for the combination optimized by the data acquisition unit 31. This makes it possible to find a more optimized combination from among the combinations that satisfy the constraint conditions.

Furthermore, according to the optimization device 1 of this embodiment, when the condition determination unit 32a determines that the optimized combination does not satisfy the constraint conditions, the information update unit 32b changes the evaluation value of the optimized combination using a penalty value corresponding to the constraint conditions, thereby ensuring that the constraint information is included in the new basic information. This makes it possible to find a more optimized combination from among the combinations that satisfy the constraint conditions.

Furthermore, according to the optimization device 1 of this embodiment, the learning unit 34 acquires new basic information that learns the constraint conditions in accordance with a determination of whether the value obtained by adding the penalty value to the evaluation value is equal to or less than a preset reference point, and the data acquisition unit 31 acquires new data on optimized combinations using the new basic information. As a result, once data on combinations for which optimization has reached a certain level has been acquired, the optimization device 1 can end its solution of the combinatorial optimization problem, thereby shortening the time required to acquire data on optimized combinations.

Furthermore, according to the optimization device 1 of this embodiment, the learning unit 34 acquires new basic information in the form of binary variable optimization without quadratic constraints. This makes it possible to use Ising machines such as simulated annealing and quantum annealing to acquire data on optimized combinations.

Furthermore, according to the optimization device 1 of this embodiment, the data acquisition unit 31 acquires data on optimized combinations using a binary variable optimization solver without quadratic constraints, such as an Ising machine. This reduces the time required to acquire data on optimized combinations.

Furthermore, according to the optimization method of this embodiment, as shown in FIG. 2, in steps S4 to S7, basic information is corrected using the optimized combination data and constraint information acquired in step S2. In step S9, new basic information with constraint conditions learned is acquired using the basic information corrected in steps S4 to S7. Then, in step S10 and the step S2 following step S10, new data for the optimized combination is acquired using the new basic information with constraint conditions learned. This makes it possible to determine, for example, optimized combinations from combinations that satisfy constraint conditions that are difficult to formulate. Furthermore, in the second and subsequent steps of step S9, new basic information with further constraint conditions learned is acquired using the new data for the optimized combination acquired in step S10 and the step S2 following step S10 and new basic information corrected using the constraint information. In this way, by sequentially repeating the acquisition of optimized combination data in step S10 and the step S2 following step S10, and the acquisition of basic information with constraint conditions learned in step S9, it is possible to determine even more optimized combinations from among combinations that satisfy constraint conditions.

Furthermore, according to the computer program of this embodiment, the correction function corrects the basic information using the data of the optimized combination acquired by the first data acquisition function and the constraint information. The learning function uses the basic information corrected by the correction function to acquire new basic information that has learned the constraint conditions, and the second data acquisition function uses the new basic information that has learned the constraint conditions to acquire new data of the optimized combination. This makes it possible, for example, to determine an optimized combination from among combinations that satisfy constraint conditions that are difficult to formulate. Furthermore, using the new data of the optimized combination acquired by the second data acquisition function and the constraint information, the learning function acquires further new basic information that has further learned the constraint conditions. In this way, by sequentially repeating the acquisition of data of the optimized combination and the acquisition of basic information that has learned the constraint conditions, it is possible to determine a further optimized combination from among combinations that satisfy the constraint conditions.

<Modification of this embodiment>
The present invention is not limited to the above-described embodiment, and can be embodied in various forms without departing from the spirit of the invention. For example, the following modifications are also possible.

[Modification 1]
In the above-described embodiment, the correction unit 32 includes a condition determination unit 32a that determines whether the optimized combination acquired by the data acquisition unit 31 satisfies the constraint conditions included in the constraint information, and an information update unit 32b that updates the basic information in accordance with the determination result of the condition determination unit 32a. The configuration of the correction unit 32 is not limited to this. It is sufficient if the basic information can be corrected in consideration of the constraint conditions using the data of the optimized combination acquired by the data acquisition unit 31 and the constraint information.

[Modification 2]
2, in the above-described embodiment, in response to the result of the determination by the evaluation/determination unit 32c, the relationship between the input x and the evaluation value y is learned by Bayesian estimation in step S9, and in step S10, a new input x that is estimated to be the optimal input is estimated based on the relationship estimated in step S9. The method of estimating the new input x is not limited to this.

[Modification 3]
In the above embodiment, the learning unit 34 acquires new basic information in the form of binary variable optimization without quadratic constraints. However, the learning format of the learning unit 34 is not limited to this.

[Modification 4]
In the above-described embodiment, the data acquisition unit 31 acquires data of optimized combinations using a binary variable optimization solver without quadratic constraints, such as an Ising machine. However, the method for acquiring data of combinations by the data acquisition unit 31 is not limited to this.

This aspect has been described above based on embodiments and variations, but the above-described embodiments are intended to facilitate understanding of this aspect and are not intended to limit this aspect. This aspect may be modified or improved without departing from its spirit or the scope of the claims, and equivalents are included in this aspect. Furthermore, if a technical feature is not described as essential in this specification, it may be deleted as appropriate.

<Application Example 1>
An optimization device for solving a combinatorial optimization problem with constraints, comprising:
an input unit into which basic information regarding basic components of a combination and constraint information regarding the constraint conditions are input;
a data acquisition unit that acquires data of an optimized combination using the basic information;
a correction unit that corrects the basic information using the optimized combination data acquired by the data acquisition unit and the constraint information;
a learning unit that acquires new basic information that has learned the constraint conditions using the basic information corrected by the correction unit,
the data acquisition unit acquires new data of an optimized combination using the new basic information acquired by the learning unit;
the correction unit corrects the new basic information acquired by the learning unit using the new data of the optimized combination acquired by the data acquisition unit and the constraint information;
the learning unit further learns the constraint conditions using the new basic information corrected by the correction unit, and acquires further new basic information.
Optimizer.
<Application Example 2>
The optimization device according to Application Example 1,
The correction unit
a condition determination unit that determines whether the optimized combination acquired by the data acquisition unit satisfies the constraint condition;
an information update unit that updates the basic information when the condition determination unit determines that the optimized combination does not satisfy the constraint condition,
Optimizer.
<Application Example 3>
The optimization device according to Application Example 1 or Application Example 2,
the data acquisition unit calculates an evaluation value of the optimized combination;
when the condition determination unit determines that the optimized combination does not satisfy the constraint condition, the information update unit updates the basic information by changing the evaluation value using a penalty value corresponding to the constraint condition.
Optimizer.
<Application Example 4>
The optimization device according to any one of Application Examples 1 to 3 further comprises:
an evaluation determination unit that determines whether a corrected evaluation value obtained by adding the penalty value to the evaluation value is equal to or less than a predetermined reference score;
When the evaluation determination unit determines that the corrected evaluation value is greater than the reference point, the learning unit uses the basic information updated by the information update unit to obtain new basic information that has learned the constraint condition.
Optimizer.
<Application Example 5>
The optimization device according to any one of Application Examples 1 to 4,
The learning unit acquires new basic information in the form of a binary variable optimization without quadratic constraints.
Optimizer.
<Application Example 6>
The optimization device according to any one of Application Examples 1 to 5,
the data acquisition unit acquires data of the optimized combination using a binary variable optimization solver without quadratic constraints;
Optimizer.
<Application Example 7>
An optimization method for solving a combinatorial optimization problem with constraints using an optimization device, comprising:
an input step of inputting basic information on basic components of a combination and constraint information on the constraint conditions;
a first data acquisition step of acquiring data of an optimized combination using the basic information;
a correction step of correcting the basic information using the optimized combination data acquired in the first data acquisition step and the constraint information;
a learning step of acquiring new basic information by learning the constraint conditions using the basic information corrected in the correction step;
a second data acquisition step of acquiring new data of an optimized combination using new basic information acquired in the learning step,
Optimization methods.
<Application Example 8>
A computer program that causes a computer to solve a combinatorial optimization problem subject to constraints,
an input function for inputting basic information regarding the basic components of the combination and constraint information regarding the constraint conditions;
a first data acquisition function that acquires data of an optimized combination using the basic information;
a correction function that corrects the basic information using the optimized combination data acquired by the first data acquisition function and the constraint information;
a learning function that acquires new basic information that has learned the constraints using the basic information corrected by the correction function; and
a second data acquisition function that acquires new data of an optimized combination using new basic information acquired by the learning function;
Computer program.

DESCRIPTION OF SYMBOLS 1... Optimization device 10... Input unit 50... Transmitting/receiving unit 31... Data acquisition unit 32... Correction unit 32a... Condition determination unit 32b... Information update unit 33... Evaluation determination unit 34... Learning unit

Claims (8)

An optimization device for solving a combinatorial optimization problem with constraints, comprising:
an input unit into which basic information regarding basic components of a combination and constraint information regarding the constraint conditions are input;
a data acquisition unit that acquires data of an optimized combination using the basic information;
a correction unit that corrects the basic information using the optimized combination data acquired by the data acquisition unit and the constraint information;
a learning unit that acquires new basic information that has learned the constraint conditions using the basic information corrected by the correction unit,
the data acquisition unit acquires new data of an optimized combination using the new basic information acquired by the learning unit;
the correction unit corrects the new basic information acquired by the learning unit using the new data of the optimized combination acquired by the data acquisition unit and the constraint information;
the learning unit further learns the constraint conditions using the new basic information corrected by the correction unit, and acquires further new basic information.
Optimizer. 2. The optimization device according to claim 1,
The correction unit
a condition determination unit that determines whether the optimized combination acquired by the data acquisition unit satisfies the constraint condition;
an information update unit that updates the basic information when the condition determination unit determines that the optimized combination does not satisfy the constraint condition,
Optimizer. 3. The optimization device according to claim 2,
the data acquisition unit calculates an evaluation value of the optimized combination;
when the condition determination unit determines that the optimized combination does not satisfy the constraint condition, the information update unit updates the basic information by changing the evaluation value using a penalty value corresponding to the constraint condition.
Optimizer. The optimization device according to claim 3 further comprises:
an evaluation determination unit that determines whether a corrected evaluation value obtained by adding the penalty value to the evaluation value is equal to or less than a predetermined reference score;
When the evaluation determination unit determines that the corrected evaluation value is greater than the reference point, the learning unit uses the basic information updated by the information update unit to obtain new basic information that has learned the constraint condition.
Optimizer. 3. The optimization device according to claim 1 or 2,
The learning unit acquires new basic information in the form of a binary variable optimization without quadratic constraints.
Optimizer. 3. The optimization device according to claim 1 or 2,
the data acquisition unit acquires data of the optimized combination using a binary variable optimization solver without quadratic constraints;
Optimizer. An optimization method for solving a combinatorial optimization problem with constraints using an optimization device, comprising:
an input step of inputting basic information on basic components of a combination and constraint information on the constraint conditions;
a first data acquisition step of acquiring data of an optimized combination using the basic information;
a correction step of correcting the basic information using the optimized combination data acquired in the first data acquisition step and the constraint information;
a learning step of acquiring new basic information by learning the constraint conditions using the basic information corrected in the correction step;
a second data acquisition step of acquiring new data of an optimized combination using new basic information acquired in the learning step,
Optimization methods. A computer program that causes a computer to solve a combinatorial optimization problem subject to constraints,
an input function for inputting basic information regarding the basic components of the combination and constraint information regarding the constraint conditions;
a first data acquisition function that acquires data of an optimized combination using the basic information;
a correction function that corrects the basic information using the optimized combination data acquired by the first data acquisition function and the constraint information;
a learning function that acquires new basic information that has learned the constraints using the basic information corrected by the correction function; and
a second data acquisition function that acquires new data of an optimized combination using new basic information acquired by the learning function;
Computer program.