Information processing device, solution method, and computer-readable recording medium storing solution program

An information processing method implemented by a computer, the information processing method comprising:

• receiving, from a user terminal, target problem information including a linear programming problem and an allowable time, the allowable time being a time value set as a time limit for a computational time required to solve the linear programming problem;
• determining a division granularity when the linear programming problem is divided into a plurality of partial problems on a basis of the allowable time indicated by the received target problem information, the determining of the division granularity including searching for, based on a prediction model indicating a correspondence relationship between problem size and solution time, a maximum problem size that is solved within the allowable time to determine the division granularity on a basis of the searched maximum problem size, the prediction model having a characteristic such that the solution time exponentially increases with increasing problem size for the linear programming problem;
• creating an objective function of each of the partial problems divided from the linear programming problem on a basis of the determined division granularity from an objective function of the linear programming problem;
• creating, for each partial problem of the partial problems, a first constraint expression and a second constraint expression, the creating of the first and second constraint expressions including:
• extracting, as the first constraint expression, a constraint expression that consists of only variables included in the each partial problem from a constraint expression group of the linear programming problem,
• extracting terms including only variables included in the each partial problem from remaining constraint expressions, excluding the first constraint expression, of the constraint expression group,
• referring to past allocation result data regarding variables included in the linear programming problem to specify a value for each term of the extracted terms, and
• creating, as the second constraint expression, a constraint expression that includes each term of the extracted terms on a basis of the specified value of each term of the terms, thereby reducing a problem size of the each partial problem;
• and
• obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on a basis of the objective function and the first and second constraint expressions created for each of the partial problems.

A non-transitory computer-readable storage medium storing an information processing program for causing a computer to execute processing, the processing including:

• receiving, from a user terminal, target problem information including a linear programming problem and an allowable time, the allowable time being a time value set as a time limit for a computational time required to solve the linear programming problem;
• determining a division granularity when the linear programming problem is divided into a plurality of partial problems on a basis of the allowable time indicated by the received target problem information, the determining of the division granularity including searching for, based on a prediction model indicating a correspondence relationship between problem size and solution time, a maximum problem size that is solved within the allowable time to determine the division granularity on a basis of the searched maximum problem size, the prediction model having a characteristic such that the solution time exponentially increases with increasing problem size for the linear programming problem;
• creating an objective function of each of the partial problems divided from the linear programming problem on a basis of the determined division granularity from an objective function of the linear programming problem;
• creating, for each partial problem of the partial problems, a first constraint expression and a second constraint expression, the creating of the first and second constraint expressions including:
• extracting, as the first constraint expression, a constraint expression that consists of only variables included in the each partial problem from a constraint expression group of the linear programming problem,
• extracting terms including only variables included in the each partial problem from remaining constraint expressions, excluding the first constraint expression, of the constraint expression group,
• referring to past allocation result data regarding variables included in the linear programming problem to specify a value for each term of the extracted terms, and
• creating, as the second constraint expression, a constraint expression that includes each term of the extracted terms on a basis of the specified value of each term of the terms, thereby reducing a problem size of the each partial problem;
• and
• obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on a basis of the objective function and the first and second constraint expressions created for each of the partial problems.