JP7617820B2 - Constraint condition optimization device and constraint condition optimization method - Google Patents

Description

The present invention relates to an information processing device and information processing method that adjusts constraint conditions in an optimization problem.

Conventionally, the technology described in Patent Document 1 is known as a method for solving optimization problems using multiple constraints.

US Patent Application Publication No. 2014/0156334

Patent Document 1 describes how, in optimizing a portfolio using multiple constraint conditions, the results of a sensitivity analysis for each constraint condition are generated and presented to the user, and the user sets upper and lower limits for each constraint condition from the presented information. However, when there are many constraint conditions, the computational processing load for performing the sensitivity analysis is large, and the load on the user when setting the upper and lower limits for each constraint condition is also large, so there is an issue that the method of Patent Document 1 is difficult to implement.

In view of the above problems, the present invention aims to provide a technology that can appropriately adjust constraint conditions in an optimization problem.

The constraint condition optimization device according to the present invention includes a definition information acquisition unit that acquires definition information including constraint conditions set for a plurality of variables and initial values of weights of the constraint conditions, a reference solution calculation unit that calculates a reference solution that represents an optimal combination of the plurality of variables based on the definition information acquired by the definition information acquisition unit, a neighborhood solution calculation unit that calculates, for each of a plurality of scenarios set in advance, a neighborhood solution that represents an optimal combination of the plurality of variables when the weights of the constraint conditions are changed from their initial values, and a calculation result of the neighborhood solution for each of the plurality of scenarios. and a user presentation unit that presents to the user, wherein the scenario includes information on a constraint condition among the plurality of constraint conditions for which weighting is to be adjusted and information on the degree of deviation of the variable corresponding to the constraint condition from a target value, and the constraint conditions for which weighting is to be adjusted are set differently for each of the plurality of scenarios, and the user presentation unit displays on a display monitor a screen including the degree of deviation for each constraint condition in each neighborhood solution and a total number of constraint conditions in which the variable deviates from the target value in each neighborhood solution, to present the calculation results of the neighborhood solution for each scenario to the user .
A constraint optimization method according to the present invention acquires definition information including constraint conditions set for a plurality of variables and initial values of weights of the constraint conditions, calculates a reference solution representing an optimal combination of the plurality of variables based on the acquired definition information by a computer, and calculates a neighborhood solution representing an optimal combination of the plurality of variables when the weights of the constraint conditions are changed from their initial values based on a plurality of preset scenarios by the computer for each of the scenarios, the scenarios including information on constraint conditions whose weights are to be adjusted among the plurality of constraint conditions and information on the deviation of the variables corresponding to the constraint conditions from target values, the plurality of scenarios having constraint conditions whose weights are to be adjusted differently for each of the scenarios, and displays a screen including the deviation for each of the constraint conditions in each neighborhood solution and the total number of the constraint conditions in which the variables in each neighborhood solution deviate from the target value on a display monitor to present the calculation results of the neighborhood solutions for each of the scenarios to a user .

The present invention provides a technology that can appropriately adjust constraints in an optimization problem.

3 is a flowchart outlining a constraint adjustment method according to the present invention. FIG. 1 is a diagram showing an example of a hardware configuration of an information processing device for implementing constraint condition adjustment according to the present invention. 1 is a diagram showing an example of functional blocks of an information processing apparatus according to a first embodiment of the present invention; FIG. 4 is a diagram showing an example of a variable DB. FIG. 13 is a diagram showing an example of a constraint condition DB. FIG. 13 is a diagram showing an example of a neighboring point DB. FIG. 13 is a diagram showing an example of a variable/constraint DB. FIG. 4 is a diagram showing an example of a facility/variable DB. FIG. 4 is a diagram showing an example of a scenario/constraint condition DB. FIG. 4 is a diagram showing an example of a scenario DB. FIG. 13 is a diagram showing an example of a calculation history DB. 4 is a flowchart showing the flow of a constraint condition adjustment process according to the first embodiment of the present invention. 11 is a flowchart showing details of a neighborhood solution calculation process. FIG. 13 is a diagram showing an example of a neighborhood solution display screen. 1 is a diagram showing an example of functional blocks of an information processing apparatus according to a first embodiment of the present invention; 10 is a flowchart showing the flow of a constraint condition adjustment process according to a second embodiment of the present invention. 11 is a flowchart showing details of a screening process. FIG. 13 is a diagram showing an example of a sensitivity analysis result display screen.

The following describes an embodiment of the present invention. The present invention adjusts constraint conditions for each variable in an optimization problem in which the optimal combination of multiple variables is found through computation. For clarity of explanation, the following description and drawings have been omitted or simplified as appropriate. The present invention is not limited to the following embodiment, and all application examples that meet the concept of the present invention are included in the technical scope of the present invention. Unless otherwise specified, each component may be multiple or singular.

(Summary of the Invention)
1 is a flowchart showing an outline of a constraint condition adjustment method according to the present invention. In the present invention, constraint conditions are adjusted by executing the processes of steps S101 to S105 shown in the flowchart of FIG.

In step S101, definition information used to generate a model for solving the optimization problem is obtained. In step S102, a model for solving the optimization problem is generated using the definition information obtained in step S101. In step S103, a reference solution for a combination of multiple variables is calculated using the optimization model generated in step S102. In step S104, the constraint conditions for each variable for which a reference solution was calculated in step S103 are adjusted, and a neighboring solution to the reference solution is calculated. In step S105, the neighboring solutions found in step S104 are presented to the user.

Next, the hardware configuration of an information processing device according to one embodiment of the present invention will be described. FIG. 2 is a diagram showing an example of the hardware configuration of an information processing device for implementing constraint condition adjustment according to the present invention.

As shown in FIG. 2, the information processing device 100 according to this embodiment includes a processor 101, a memory 102, a storage device 103, a communication interface (IF) 104, and an input/output IF 105.

The processor 101 uses the memory 102 as a working area and executes a predetermined program stored in the storage device 103 to realize various functions of the information processing device 100. The memory 102 is formed by combining, for example, a read only memory (ROM) and a random access memory (RAM).

The storage device 103 stores and holds various programs executed by the processor 101 and various data used when executing the programs. The storage device 103 is configured using non-volatile recording media such as a hard disk drive (HDD), a solid state drive (SSD), a magneto-optical disk, or a flash memory. Note that the number and type of recording media used as the storage device 103 are not important as long as they are capable of storing the programs and data required by the information processing device 100.

The communication IF 104 performs interface processing for communication data transmitted and received between various external devices connected to the information processing device 100. In this embodiment, a POS (Point Of Sales) system 110 capable of collecting various customer information such as sales information for each product, and a production management system 120 which manages the production of products are connected to the information processing device 100 as external devices via the communication IF 104. Note that other external devices may also be connectable to the information processing device 100.

An input device 130 and an output device 140 are connected to the information processing device 100. The input device 130 is composed of, for example, a keyboard, a mouse, a touch panel, etc., and detects input operations by a user using the information processing device 100, and outputs operation information corresponding to the detection result to the information processing device 100. This operation information is input to the processor 101 via the input/output IF 105, and is reflected in the processing of the processor 101. The output device 140 is composed of, for example, a display monitor, a printer, etc., and presents this information to the user by performing screen display, printing, etc. based on the image information and text information output from the processor 101 via the input/output IF 105.

(First embodiment)
Next, an embodiment of the functional configuration of an information processing device for implementing the constraint condition adjustment of the present invention will be described. Fig. 3 is a diagram showing an example of functional blocks of the information processing device according to the first embodiment of the present invention.

As shown in FIG. 3, the information processing device 100 according to this embodiment includes the functions of a definition information acquisition unit 201, a reference solution calculation unit 202, a neighborhood solution calculation unit 203, a scenario setting unit 204, and a user presentation unit 205. These functions are realized by the processor 101 executing a predetermined program in the hardware configuration of FIG. 2, for example. The storage device 103 also stores the following databases: a variable DB 211, a constraint DB 212, a neighborhood point DB 213, a variable/constraint DB 214, a facility/variable DB 215, a scenario/constraint DB 216, a scenario DB 217, and a calculation history DB 218. Details of these databases will be described later with reference to FIGS. 4 to 11.

The definition information acquisition unit 201 acquires definition information required to generate a model for solving an optimization problem from external devices such as the POS system 110 and the production management system 120 (see FIG. 2) connected to the information processing device 100, and stores the information in the variable DB 211, the constraint DB 212, the variable/constraint DB 214, and the facility/variable DB 215. This definition information includes, for example, information on functions that model and represent each element of the object to be dealt with in the optimization problem, information on variables that represent the parameters of the function according to the state of each element, information on constraints set for each variable, and information on the initial value of the weight of each constraint. The process performed by the definition information acquisition unit 201 corresponds to step S101 in the flowchart in FIG. 1.

The reference solution calculation unit 202 reads the definition information acquired by the definition information acquisition unit 201 from each database, the variable DB 211, the constraint DB 212, and the variable/constraint DB 214, and generates an optimization model based on the definition information. It then calculates an optimal combination of multiple variables in the generated optimization model, and stores the obtained combination of variables as a reference solution in the storage device 103. The processing performed by the reference solution calculation unit 202 corresponds to steps S102 and S103 in the flowchart of FIG. 1.

The neighborhood solution calculation unit 203 calculates the optimal combination of multiple variables when the weights of the constraint conditions are changed from their initial values in the optimization model generated by the reference solution calculation unit 202, and stores the obtained combination of variables in the calculation history DB 218 as a neighborhood solution. At this time, the neighborhood solution calculation unit 203 selects a constraint condition corresponding to the scenario selected by the user based on information representing the correspondence between the scenario and the constraint conditions stored in the scenario/constraint condition DB 216, and changes the weight of the constraint condition. Then, information representing the changed weight value is stored in the neighborhood point DB 213. Note that the process performed by the neighborhood solution calculation unit 203 corresponds to step S104 in the flowchart of FIG. 1.

The scenario setting unit 204 sets a scenario for selecting a constraint condition for which the weight is changed when the neighborhood solution calculation unit 203 calculates a neighborhood solution, and stores the scenario in the scenario DB 217. A scenario is information describing a combination of constraint conditions for which weights are to be adjusted, and is set, for example, according to an input operation performed by a user using the input device 130. Furthermore, the scenario setting unit 204 sets a correspondence between the scenario and the constraint conditions based on the scenario stored in the scenario DB 217, and stores the setting information in the scenario/constraint condition DB 216.

The user presentation unit 205 presents the calculation results of the neighborhood solutions stored in the calculation history DB 218 to the user. The user presentation unit 205 can present the neighborhood solutions to the user, for example, by performing a predetermined screen display on a display monitor connected to the information processing device 100 as the output device 140. The process performed by the user presentation unit 205 corresponds to step S105 in the flowchart of FIG. 1.

Next, the details of each of the databases stored in the storage device 103, namely the variable DB 211, the constraint DB 212, the neighboring points DB 213, the variable/constraint DB 214, the facility/variable DB 215, the scenario/constraint DB 216, the scenario DB 217, and the calculation history DB 218, will be described below with reference to Figures 4 to 11.

FIG. 4 is a diagram showing an example of the variable DB 211. As shown in FIG. 4, the variable DB 211 has fields for, for example, a variable ID 2111, a definition file 2112, and a process ID 2113. The variable ID 2111 stores information for uniquely identifying each variable (for example, code information such as a JAN code). The definition file 2112 stores information of a file representing the definition information of each variable in the optimization model. The definition information represented by the definition file 2112 defines an optimization model, which is a function that models each element of the object to be handled in the optimization problem, and specifies the range of each variable that changes continuously as a parameter of the optimization model. The process ID 2113 stores information representing which element each variable corresponds to in the actual object. For example, if the object represented by the optimization model is a large commercial facility such as a shopping mall, information representing each store in the facility is stored in the process ID 2113.

In the variable DB211, information on each of the above fields is stored for each record set corresponding to each variable. The upper limit on the number of records is determined according to the upper limit on the number of variables that can be set in the optimization model. For example, the upper limit on the number of variables that can be set in the optimization model can be determined in advance based on the processing power of the processor 101 in the information processing device 100. Note that the database configuration shown in FIG. 4 is an example, and the configuration of the variable DB211 is not limited to this as long as an optimization model can be appropriately defined for the object that the optimization problem deals with.

FIG. 5 is a diagram showing an example of the constraint DB 212. As shown in FIG. 5, the constraint DB 212 has fields for, for example, a constraint ID 2121, a definition file 2122, an initial weight value 2123, and a target value 2124. The constraint ID 2121 stores information such as an ID number or name as information for uniquely identifying each constraint. The definition file 2122 stores information of a file representing definition information of each constraint in the optimization model. The definition information represented by this definition file 2122 defines the content of the constraint required for each variable of the optimization model. For example, the allowable conditions for each variable can be defined according to business constraints, constraints due to physical tolerances, efficiency constraints, etc. The initial weight value 2123 stores an initial value of the weight set for each constraint. The initial value of the weight is determined in advance according to, for example, the importance of each constraint. The target value 2124 is set to a target value of the variable for each constraint.

In the constraint DB212, information on each of the above fields is stored for each record set corresponding to each constraint. Note that the database configuration shown in FIG. 5 is an example, and the configuration of the constraint DB212 is not limited to this, as long as the constraints set for each variable of the optimization model can be appropriately defined.

6 is a diagram showing an example of the neighborhood point DB 213. As shown in FIG. 6, the neighborhood point DB 213 has fields for, for example, a neighborhood point ID 2131, a constraint condition ID 2132, an updated weight value 2133, and a group ID 2134. The neighborhood point ID 2131 stores information such as an ID number as information for uniquely identifying each neighborhood point in the neighborhood solution calculated by the neighborhood solution calculation unit 203. A neighborhood point is a constraint condition in which the weight is changed from an initial value to a certain value, and is generated by the neighborhood solution calculation unit 203 when calculating a neighborhood solution. The constraint condition ID 2132 stores information similar to the constraint condition ID 2121 of the constraint condition DB 212 as information representing the constraint condition corresponding to each neighborhood point. The updated weight value 2133 stores information representing the weight value after the change at each neighborhood point. The group ID 2134 stores information on the group to which each neighborhood point belongs when each neighborhood point is grouped according to its characteristics.

In the neighborhood point DB213, information on each of the above fields is stored for each record set corresponding to each neighborhood point. Note that the database configuration shown in FIG. 6 is an example, and the configuration of the neighborhood point DB213 is not limited to this as long as it can appropriately represent each neighborhood point in the neighborhood solution.

Figure 7 is a diagram showing an example of variable/constraint DB 214. As shown in Figure 7, variable/constraint DB 214 has fields for variable ID 2141 and constraint ID 2142, for example. In variable ID 2141, information similar to variable ID 2111 in variable DB 211 is stored as information representing each variable. In constraint ID 2142, information similar to constraint ID 2121 in constraint DB 212 is stored as information representing each constraint.

In the variable/constraint DB214, information on each of the above fields is stored for each record set corresponding to each combination of variables and constraints in the optimization model. That is, the combination of variable ID2141 and constraint ID2142 stored in each record of the variable/constraint DB214 defines the constraint required for each variable in the optimization model. Note that the database configuration shown in FIG. 7 is an example, and the configuration of the variable/constraint DB214 is not limited to this as long as it can appropriately represent the correspondence between variables and constraints in the optimization model.

Figure 8 is a diagram showing an example of facility/variable DB 215. As shown in Figure 8, facility/variable DB 215 has fields for facility ID 2151 and variable ID 2152, for example. Facility ID 2151 stores information representing facilities such as factories, warehouses, and stores, as information representing which facility each variable corresponds to in the actual object. Variable ID 2152 stores information similar to variable ID 2111 of variable DB 211 as information representing each variable.

In the facility/variable DB215, information on each of the above fields is stored for each record set corresponding to each combination of the facility to which each element of the object to be dealt with in the optimization problem belongs and the variables representing each element. Note that the database configuration shown in FIG. 8 is only an example, and the configuration of the facility/variable DB215 is not limited to this as long as it can appropriately represent the correspondence between the facility to which each element of the object belongs and the variables.

9 is a diagram showing an example of the scenario/constraint DB 216. As shown in FIG. 9, the scenario/constraint DB 216 has fields such as a scenario ID 2161, a step ID 2162, a constraint ID 2163, and a constraint type 2164. The scenario ID 2161 stores information for uniquely identifying each scenario set by the scenario setting unit 204. The step ID 2162 stores information for uniquely identifying each step set for each scenario. A scenario is composed of one or more steps in order to specify in detail the constraint conditions to be applied to each variable in the calculation of a reference solution or a neighborhood solution using an optimization model. The step ID 2162 stores information representing each step of this scenario. The constraint ID 2163 stores information similar to the constraint ID 2121 of the constraint DB 212 as information representing the constraint conditions corresponding to each step of each scenario. The constraint type 2164 stores information representing the type of constraint conditions required for each variable. For example, if each variable must satisfy the applied constraint condition, "Hard" is stored in constraint type 2164 as information representing the type of the constraint condition, and if each variable can deviate to some extent from the applied constraint condition, "Soft" is stored in constraint type 2164 as information representing the type of the constraint condition.

In the scenario/constraint DB216, information on each of the above fields is stored for each record set corresponding to each constraint specified in the scenario. That is, the combination of scenario ID 2161, step ID 2162, constraint ID 2163, and constraint type 2164 stored in each record in the scenario/constraint DB216 defines the content of each scenario, the constraint conditions that are subject to weight adjustment in each scenario, and the deviation of each variable from the constraint conditions. Note that the database configuration shown in FIG. 9 is one example, and the configuration of the scenario/constraint DB216 is not limited to this as long as it can appropriately represent the constraint conditions that are specified as subject to weight adjustment in each scenario.

Figure 10 is a diagram showing an example of scenario DB 217. As shown in Figure 10, scenario DB 217 has fields for, for example, scenario ID 2171 and rule 2172. Scenario ID 2171 stores information representing each scenario, similar to scenario ID 2161 in scenario/constraint DB 216. Rule 2172 stores information describing the contents of each scenario.

In the scenario DB217, information on each of the above fields is stored for each record set corresponding to each scenario set by the scenario setting unit 204. Note that the database configuration shown in FIG. 10 is an example, and the configuration of the scenario DB217 is not limited to this as long as it can appropriately represent the contents of each scenario.

FIG. 11 is a diagram showing an example of the calculation history DB 218. As shown in FIG. 11, the calculation history DB 218 has fields for date 2181, selected scenario 2182, calculation result 2183, and evaluation 2184, for example. Date 2181 stores information indicating the date and time when each neighborhood solution was calculated by the neighborhood solution calculation unit 203. Selected scenario 2182 stores information similar to the scenario ID 2161 of the scenario/constraint DB 216 as information indicating the scenario selected by the user at the time of calculation for each neighborhood solution. Calculation result 2183 stores information on data indicating the calculation result of each neighborhood solution. Evaluation 2184 stores an evaluation type such as "Best" or "Moderate" as information indicating the evaluation result of each neighborhood solution.

In the calculation history DB218, information in each of the above fields is stored for each record set corresponding to each neighborhood solution calculated by the neighborhood solution calculation unit 203. Note that the database configuration shown in FIG. 11 is an example, and the configuration of the calculation history DB218 is not limited to this as long as it can appropriately represent the calculation results of each neighborhood solution.

Fig. 12 is a flowchart showing the flow of the constraint condition adjustment process according to the first embodiment of the present invention. The process shown in the flowchart in Fig. 12 is executed by the processor 101 in response to an instruction from a user in the hardware configuration of Fig. 2, for example.

In step S210, the processor 101, through the definition information acquisition unit 201, acquires definition information used to generate a model for solving the optimization problem. Here, for example, based on an input operation from the user, a list of variables to be optimized and a list of constraint conditions for each variable are acquired, and definition information is acquired from the contents of these and stored in each database of the variable DB 211, the constraint DB 212, the variable/constraint DB 214, and the facility/variable DB 215.

In step S220, the processor 101 reads the definition information acquired in step S210 from each database using the reference solution calculation unit 202, and generates an optimization model based on this. Here, the optimization model can be generated by generating an arithmetic expression for a function that models each element of the object to be dealt with in the optimization problem, for example, using a well-known calculation method.

In step S230, the processor 101 uses the reference solution calculation unit 202 to calculate a reference solution based on the optimization model generated in step S220. Here, among the combinations of variables that satisfy the constraint conditions set for each variable in the calculation formula representing the optimization model, the optimal combination of variables whose calculated value of the calculation formula satisfies the desired conditions is found as the reference solution of the optimization problem. For example, a combination of variables that maximizes or minimizes the calculated value of the calculation formula, or a combination of variables that produces a calculated value that is the smallest difference from a specified target value, can be found using a well-known optimization calculation algorithm or the like. Once the reference solution has been calculated in step S230, the processor 101 stores the calculation result in the storage device 103 and proceeds to the next step S240.

In step S240, the processor 101 selects one of the scenarios that have been set in advance by the scenario setting unit 204 and stored in the scenario DB 217. Here, for example, the scenarios stored in the scenario DB 217 are selected in order from the top as scenarios for which nearby solutions are to be generated. Alternatively, one of the scenarios may be selected based on an input operation from the user.

In step S250, the processor 101 performs a neighborhood solution calculation process using the neighborhood solution calculation unit 203. In this neighborhood solution calculation process, a constraint condition to be subjected to weight adjustment is selected based on the scenario selected in step S240, and the weight of the constraint condition is changed from the initial value when the reference solution was calculated in step S230. Then, the optimal combination of variables for the changed weight is obtained as a neighborhood solution for the reference solution. Details of the neighborhood solution calculation process in step S250 will be described later with reference to FIG. 13.

In step S260, the processor 101 judges whether or not to end the neighborhood solution calculation process in step S250. For this judgment, for example, for each scenario stored in the scenario DB 217, whether or not the neighborhood solution has been calculated is confirmed. As a result, if there is a scenario for which the neighborhood solution has not yet been calculated, it is judged that the neighborhood solution calculation process is to be continued, one of the current neighborhood solutions is selected as a new reference solution, and the process returns to step S240 to select another scenario. On the other hand, if the neighborhood solutions have been calculated for all scenarios, it is judged that the neighborhood solution calculation process is to be ended, and the process proceeds to the next step S270. As an example of a method for selecting the neighborhood solution at this time, the one with the smallest deviation from the constraint condition specified by the current scenario may be selected, or the one with the smallest penalty function value described later may be selected. Furthermore, at this time, it is judged based on the user's input operation whether or not the user wishes to end the neighborhood solution calculation process, and if the user wishes to end the neighborhood solution calculation process, it may be judged that the neighborhood solution calculation process is to be ended, and the process proceeds to the next step S270, even if there is a scenario for which the neighborhood solution has not yet been calculated.

In step S270, the processor 101 causes the user presentation unit 205 to present to the user each of the neighborhood solutions stored in the storage device 103 in the neighborhood solution calculation process in step S250. Here, the contents of the neighborhood solutions obtained for each scenario selected in step S240 are presented to the user, for example, by displaying them on the screen of a display monitor, which is the output device 140. An example of the screen displayed in step S270 will be described later with reference to FIG. 14.

After performing the processing of step S270, the processor 101 outputs the obtained calculation results to an external device such as the production management system 120, and then ends the processing shown in the flowchart of FIG. 12.

Figure 13 is a flowchart showing details of the neighborhood solution calculation process. The process shown in the flowchart in Figure 13 is executed by the processor 101 in step S250 in Figure 12 in the hardware configuration in Figure 2, for example.

In step S301, the processor 101 reads the optimization model generated in step S220 of FIG. 12.

In step S302, the processor 101 sets the constraint condition for which the weight is to be adjusted in the optimization model read in step S301, based on the scenario selected in step S240 of FIG. 12. Here, for example, in the scenario/constraint condition DB 216 of FIG. 9, a record corresponding to the selected scenario is selected, and the information stored in the constraint condition ID 2163 of that record is checked, whereby the constraint condition for which the weight is to be adjusted can be set.

In step S303, the processor 101 determines the weight value after the change of the constraint condition selected in step S302. Here, for example, the weight value of the constraint condition is changed randomly from the initial value within a predetermined adjustment range. Note that if the weight value of the constraint condition can be appropriately changed from the initial value, it is possible to determine the changed weight value in step S303 by any method.

In step S304, the processor 101 uses the neighborhood solution calculation unit 203 to calculate neighborhood solutions when the weight values determined in step S303 are set for each constraint condition. Here, for example, by using a function called a penalty function to simplify the calculation, it is possible to easily find an optimal combination of variables that satisfies each constraint condition after weight adjustment. The penalty function is a function defined based on the total value of the product of the weight and the deviation for each constraint condition, and is specifically expressed, for example, as in the following formula (1).
F _penalty = F _original + Σ (w _i ×N _i ) ... (1)

In formula (1), F _original represents a function of the optimization model generated in step S220. Furthermore, w _i represents the weight value of the i-th constraint condition, and N _i represents the deviation of the variable corresponding to the i-th constraint condition. The deviation is a value representing how far the variable corresponding to the constraint condition is from the target value stored in the target value 2124 in the constraint condition DB 212 in FIG. 5, for example. Note that if the neighborhood solution can be calculated appropriately, the neighborhood solution can be calculated in step S304 by any other method.

In step S305, the processor 101 saves the neighborhood solution obtained by the calculation in step S304 and the weight values of each constraint condition for which the neighborhood solution was obtained in the storage device 103. Specifically, for example, in the neighborhood point DB 213 of FIG. 6, a record corresponding to each constraint condition for which the weight value has been changed is added, and information on the changed weight value is stored in each field of each record as neighborhood point information. Also, in the calculation history DB 218 of FIG. 11, a record corresponding to the neighborhood solution is added, and information on the calculation result of the neighborhood solution is stored in each field of the record.

After performing the processing of step S305, the processor 101 ends the neighborhood solution calculation processing and proceeds to step S260 in FIG. 12.

Figure 14 is a diagram showing an example of a neighborhood solution display screen for presenting the contents of the neighborhood solution to the user. The neighborhood solution display screen 141 shown in Figure 14 is configured to include display frames 1411, 1421 and selection buttons 1431, 1432.

The display frame 1411 is a portion showing the contents of an arbitrary neighborhood solution (neighborhood solution 1) among the multiple neighborhood solutions obtained by the neighborhood solution calculation process, and includes a weight list 1412, a deviation graph 1413, a calculation result 1414, and a check box 1415. The weight list 1412 shows the weight value of each constraint condition when the neighborhood solution 1 is obtained. The deviation graph 1413 shows the deviation of the variable corresponding to each constraint condition from the target value. The calculation result 1414 shows the process value obtained as the calculation result of the neighborhood solution 1 and the total number of constraint conditions in which the variable deviates from the target value. The check box 1415 is a portion for selecting one of the current neighborhood solutions to be used as the next reference solution by checking it by the user's input operation.

Display frame 1421 is a portion that shows the contents of an arbitrary nearby solution (called nearby solution 2) excluding nearby solution 1 from among the multiple nearby solutions obtained by the nearby solution calculation process, and similar to display frame 1411, includes a weight list 1422, a deviation graph 1423, calculation results 1424, and a check box 1425.

After the neighborhood solution display screen 141 is displayed, when the selection button 1431 is selected by the user's input operation, the information processing device 100 continues the calculation process of the neighborhood solution. On the other hand, when the selection button 1432 is selected by the user's input operation, the information processing device 100 ends the calculation process of the neighborhood solution. By selecting either the selection button 1431 or 1432, the user can instruct the information processing device 100 whether or not to continue the calculation of the neighborhood solution.

Note that the neighborhood solution display screen shown in FIG. 14 is just one example, and other screen configurations may be used. Any screen configuration may be used as long as it can appropriately present to the user the calculation results of the neighborhood solutions for each scenario obtained by the neighborhood solution calculation process.

Second Embodiment
Next, a second embodiment of the present invention will be described. In this embodiment, an example will be described in which a method of selecting constraint conditions to be subjected to weight adjustment when calculating a neighborhood solution is performed using a method different from that of the first embodiment.

Figure 15 is a diagram showing an example of functional blocks of an information processing device according to the second embodiment of the present invention. The information processing device 100A according to this embodiment differs from the information processing device 100 of Figure 3 described in the first embodiment in that it has a screening processing unit 206 instead of a scenario setting unit 204, and that the scenario/constraint condition DB 216 and scenario DB 217 are not stored in the storage device 103.

The screening processing unit 206 acquires, for each constraint condition, the degree of influence that a change in the weight of each constraint condition has on the neighborhood solution in the optimization model generated by the reference solution calculation unit 202. The degree of influence for each constraint condition acquired by the screening processing unit 206 is presented to the user by the user presentation unit 205, and is also used by the neighborhood solution calculation unit 203 to select a constraint condition for which the weight is to be adjusted when the neighborhood solution calculation unit 203 calculates the neighborhood solution.

The hardware configuration of the information processing device 100A according to this embodiment is the same as the hardware configuration in FIG. 2 described in the first embodiment. Therefore, hereinafter, the information processing device 100A according to this embodiment will be described using the hardware configuration in FIG. 2.

Fig. 16 is a flowchart showing the flow of the constraint condition adjustment process according to the second embodiment of the present invention. The process shown in the flowchart in Fig. 16 is executed by the processor 101 in response to an instruction from a user in the hardware configuration of Fig. 2, for example.

In steps S210 to S230, the processor 101 performs the same processes as those shown in the flowchart of FIG. 12 described in the first embodiment.

After performing the process of step S230, the processor 101 performs the process of step S241. In step S241, the processor 101 performs a screening process by the screening processing unit 206. In this screening process, the degree of influence of a change in weight on a neighboring solution is obtained for each constraint condition of the optimization model generated in step S220. Then, a constraint condition whose influence degree is equal to or greater than a predetermined value is selected as a high sensitivity constraint condition, and the constraint condition is set as a target for weight adjustment. In this way, even if there are a large number of constraint conditions to be adjusted, it is possible to easily extract only the constraint conditions that affect the results of the optimization calculation, and adjust the constraint conditions so as to obtain a solution desired by the user in a short time. Details of the screening process of step S241 will be described later with reference to FIG. 17.

After performing the process of step S241, in steps S250 to S270, the processor 101 performs the same processes as those in the flowchart of FIG. 12 described in the first embodiment. However, in this embodiment, in the neighborhood solution calculation process of step S250, the weight of the constraint condition selected in the screening process of step S241 is changed from the initial value when the reference solution was calculated in step S230. Also, if it is determined in step S260 that the neighborhood solution calculation process is to be continued, the process returns to step S250. Then, after performing the process of step S270, the processor 101 outputs the obtained calculation result to an external device such as the production management system 120, and then ends the process shown in the flowchart of FIG. 16.

Figure 17 is a flowchart showing the details of the screening process. The process shown in the flowchart in Figure 17 is executed by the processor 101 in step S241 in Figure 16 in the hardware configuration in Figure 2, for example.

In step S401, the processor 101 reads the optimization model generated in step S220 of FIG. 16.

In step S402, the processor 101 selects one of the constraints of the optimization model loaded in step S401.

In step S403, the processor 101 performs a sensitivity analysis on the constraint condition selected in step S402 using the screening processing unit 206. Sensitivity analysis is a process of analyzing the relationship between the change in the weight of the constraint condition required for each variable of the arithmetic expression representing the optimization model and the calculated value obtained by calculating the arithmetic expression. Specifically, for example, sensitivity analysis can be performed by checking the change in the calculated value of the arithmetic expression when the weight of the constraint condition is changed within a specified range. Note that in step S403, sensitivity analysis may be performed using a method other than this.

In step S404, the processor 101 determines whether or not all constraint conditions included in the optimization model have been selected in the sensitivity analysis in step S403. If there are unselected constraint conditions, the process returns to step S402 to select one of them, and then repeats the process of step S403. If all constraint conditions have been selected, the process proceeds to the next step S405.

In step S405, the processor 101 uses the screening processing unit 206 to group the constraint conditions based on the sensitivity analysis results of step S403 for each constraint condition. Here, for example, constraint conditions that tend to change in the calculated value of the arithmetic expression in response to changes in weight are classified into the same group, thereby classifying each constraint condition into a plurality of groups. Specifically, for example, each constraint condition can be grouped into a group of constraint conditions in which the weight increase/decrease direction is the same as the calculated value increase/decrease direction, a group of constraint conditions in which the weight increase/decrease direction is opposite to the calculated value increase/decrease direction, and a group of constraint conditions in which the calculated value hardly changes in response to increases/decrease in weight. Furthermore, at this time, the grouping may be further subdivided taking into account the amount of increase/decrease in the calculated value. Note that the method of grouping is not limited to this, as long as the constraint conditions can be appropriately grouped according to the results of the sensitivity analysis.

In step S406, the processor 101 causes the user presentation unit 205 to present to the user the results of the sensitivity analysis of each constraint condition performed in step S403. Here, the results of the sensitivity analysis are presented to the user by displaying the results of grouping each constraint condition in step S405 on a screen, for example, on a display monitor, which is the output device 140. An example of the screen displayed in step S406 will be described later with reference to FIG. 18.

In step S407, the processor 101 sets the constraint conditions to be subjected to weight adjustment when performing the neighborhood solution calculation process in step S250 of FIG. 16 based on the results of the sensitivity analysis of each constraint condition performed in step S403. Here, for example, based on the grouping results of step S405, each constraint condition included in the high sensitivity group is set as a weight adjustment target. Note that the high sensitivity group is a group of constraint conditions in which the increase or decrease in the calculated value is relatively large compared to the increase or decrease in the weight. In addition to this, any constraint condition can be set as a weight adjustment target based on the results of the sensitivity analysis. For example, it is also possible to select the constraint condition to be set as a weight adjustment target according to the input operation performed by the user on the sensitivity analysis results presented in step S406.

After performing the processing of step S407, the processor 101 ends the screening processing and proceeds to step S250 in FIG. 16.

Figure 18 is a diagram showing an example of a sensitivity analysis result display screen for presenting the sensitivity analysis results to the user. The sensitivity analysis result display screen 181 shown in Figure 18 shows how the process values (calculated values of the arithmetic formula) change with respect to changes in weighting for each constraint condition belonging to groups 1 to 3.

Note that the sensitivity analysis result display screen shown in FIG. 18 is just one example, and other screen configurations may be used. Any screen configuration may be used as long as it can properly present to the user the increase/decrease tendency of the calculated value of the arithmetic formula in response to changes in the weighting for each constraint condition obtained by the sensitivity analysis.

The above-described embodiments of the present invention provide the following advantages:

(1) The information processing device 100, 100A includes a definition information acquisition unit 201 that acquires definition information including constraint conditions set for multiple variables and initial values of weights of the constraint conditions, a reference solution calculation unit 202 that calculates a reference solution that represents an optimal combination of multiple variables based on the definition information acquired by the definition information acquisition unit 201, and a neighborhood solution calculation unit 203 that calculates a neighborhood solution that represents an optimal combination of multiple variables when the weights of the constraint conditions are changed from their initial values. This makes it possible to appropriately adjust the constraint conditions in the optimization problem.

(2) The neighborhood solution calculation unit 203 in the information processing device 100 calculates neighborhood solutions based on a preset scenario (steps S240, S250). The scenario includes information on the constraint condition (constraint condition ID 2163, rule 2172) for which weighting is to be adjusted among multiple constraint conditions, and information on the deviation of variables from the constraint condition (constraint type 2164, rule 2172). This makes it easy to select the constraint condition for which weighting is to be adjusted when calculating neighborhood solutions.

(3) The neighborhood solution calculation unit 203 in the information processing device 100 can calculate the neighborhood solution by using a penalty function F _penalty based on the total value of the product of the weight and the deviation for each constraint condition (step S304). In this way, the neighborhood solution can be easily found by a simplified calculation process.

(4) The information processing device 100 includes a user presentation unit 205 that presents the calculation results of the neighborhood solutions for each of a plurality of scenarios to the user (step S270, FIG. 14). In this way, the calculation results of the neighborhood solutions can be presented to the user in an easy-to-understand manner.

(5) The information processing device 100A includes a screening processing unit 206 that acquires the degree of influence of a change in weight on a neighboring solution for each of a plurality of constraint conditions, and a user presentation unit 205 that presents the degree of influence for each constraint condition acquired by the screening processing unit 206 to the user (steps S241, S406, FIG. 18). In this manner, the degree of influence of a change in the weight of each constraint condition on a neighboring solution can be presented to the user in an easy-to-understand manner. Furthermore, even when there are a large number of constraint conditions to be adjusted, it is possible to easily extract only those constraint conditions that affect the results of the optimization calculation, and adjust the constraint conditions so that the user can obtain the solution he or she desires in a short period of time.

The present invention is not limited to the above embodiment, and can be implemented using any components without departing from the spirit of the invention.

The above embodiments and modifications are merely examples, and the present invention is not limited to these contents as long as the characteristics of the invention are not impaired. In addition, although various embodiments and modifications have been described above, the present invention is not limited to these contents. Other aspects that are conceivable within the scope of the technical ideas of the present invention are also included within the scope of the present invention.

Reference Signs List 100, 100A: Information processing device 101: Processor 102: Memory 103: Storage device 104: Communication interface 105: Input/output interface 110: POS system 120: Production management system 130: Input device 140: Output device 201: Definition information acquisition unit 202: Reference solution calculation unit 203: Neighborhood solution calculation unit 204: Scenario setting unit 205: User presentation unit 206: Screening processing unit 211: Variable DB
212...Constraint condition DB
213...neighborhood point DB
214...Variable/constraint DB
215...Facility/variable DB
216...Scenario/constraint condition DB
217...Scenario DB
218...Calculation history DB

Claims (8)

a definition information acquisition unit that acquires definition information including constraint conditions set for a plurality of variables and initial values of weights of the constraint conditions;
a reference solution calculation unit that calculates a reference solution that represents an optimal combination of the plurality of variables based on the definition information acquired by the definition information acquisition unit;
a neighborhood solution calculation unit that calculates , for each of a plurality of scenarios set in advance, a neighborhood solution that represents an optimal combination of the plurality of variables when the weights of the constraint conditions are changed from the initial values; and
a user presentation unit that presents to a user a calculation result of the neighborhood solution for each of the multiple scenarios ,
the scenario includes information on a constraint condition, among the plurality of constraint conditions, whose weight is to be adjusted, and information on a deviation degree from a target value of the variable corresponding to the constraint condition;
The plurality of scenarios are set such that the constraint conditions for which the weights are to be adjusted differ from one another for each scenario;
The user presentation unit displays on a display monitor a screen including the degree of deviation for each constraint condition in each neighborhood solution and the total number of constraint conditions in which the variables deviate from the target value in each neighborhood solution, thereby presenting the calculation results of the neighborhood solutions for each scenario to the user . 2. The constraint-based optimization apparatus according to claim 1,
A scenario setting unit that sets a plurality of the scenarios,
The scenario setting unit is a constraint condition optimization device that sets, for each of a plurality of scenarios, one or more steps that constitute the scenario, the constraint conditions corresponding to each step, and the type of the constraint conditions required for the variables at each step. 2. The constraint-based optimization apparatus according to claim 1 ,
The neighborhood solution calculation unit is a constraint condition optimization device that calculates the neighborhood solution using a penalty function based on the total value of the product of the weight and the deviation for each constraint condition. 2. The constraint-based optimization apparatus according to claim 1,
a screening processing unit that acquires, for each of a plurality of constraint conditions, a degree of influence of a change in the weight on the neighboring solutions;
The user presentation unit is a constraint condition optimization device that presents the degree of influence for each constraint condition acquired by the screening processing unit to the user. Obtaining definition information including constraint conditions set for a plurality of variables and initial values of weights of the constraint conditions;
Calculating a reference solution representing an optimal combination of the plurality of variables by a computer based on the obtained definition information;
calculating, for each of a plurality of preset scenarios, a neighborhood solution that represents an optimal combination of the plurality of variables when the weights of the constraint conditions are changed from the initial values by the computer ;
the scenario includes information on a constraint condition, among the plurality of constraint conditions, whose weight is to be adjusted, and information on a deviation degree from a target value of the variable corresponding to the constraint condition;
The plurality of scenarios are set such that the constraint conditions for which the weights are to be adjusted differ from one another for each scenario;
A constraint optimization method, which displays on a display monitor a screen including the degree of deviation for each constraint condition in each neighborhood solution and the total number of constraint conditions in which the variables deviate from the target value in each neighborhood solution, and presents the calculation results of the neighborhood solutions for each scenario to a user . 6. The constraint optimization method according to claim 5,
A constraint optimization method in which, for each of a plurality of scenarios, the computer sets one or more steps constituting the scenario, the constraint conditions corresponding to each step, and the types of the constraint conditions required for the variables at each step. 6. The constraint optimization method according to claim 5 ,
A constraint condition optimization method for calculating the neighborhood solution using a penalty function based on the total value of the product of the weight and the deviation for each constraint condition. 6. The constraint optimization method according to claim 5 ,
obtaining, for each of the plurality of constraint conditions, a degree of influence of a change in the weight on the neighboring solutions;
The constraint condition optimization method includes presenting the degree of influence for each of the acquired constraint conditions to the user.

Images