# US 2023/0068699 A1 · Information processing device, solution method, and computer-readable recording medium storing solution program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0068699 A1
- Document ID: US20230068699A1
- Status: Published application
- Kind: A1
- Application number: 17/842,859
- Filed: 2022-06-17
- Published: 2023-03-02
- Earliest claimed: 2021-09-01
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Hiroshi Otsuka
- Web page: https://patentgrep.com/patent/US20230068699A1

## CPC

- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 17/12: Simultaneous equations {, e.g. systems of linear equations}
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

An information processing device configured to perform processing, the processing including: determining a division granularity when a linear programming problem is divided into a plurality of partial problems on the basis of an allowable time needed to solve the linear programming problem to be solved; creating an objective function of each of partial problems divided from the linear programming problem on the basis of the determined division granularity from an objective function of the linear programming problem; creating a constraint expression of each of the partial problems on the basis of a constraint expression group of the linear programming problem and past allocation result data regarding a variable included in the linear programming problem; and obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on the basis of the objective function and the constraint expression created for each of the partial problems.

## Claims

### Claim 1

An information processing device comprising:
a memory; and
a processor coupled to the memory, the processor being configured to perform processing, the processing including:
determining a division granularity when a linear programming problem is divided into a plurality of partial problems on the basis of an allowable time needed to solve the linear programming problem to be solved;
creating an objective function of each of partial problems divided from the linear programming problem on the basis of the determined division granularity from an objective function of the linear programming problem;
creating a constraint expression of each of the partial problems on the basis of a constraint expression group of the linear programming problem and past allocation result data regarding a variable included in the linear programming problem; and
obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on the basis of the objective function and the constraint expression created for each of the partial problems.

### Claim 2 (depends on 1)

The information processing device according to claim 1, wherein the creating of the constraint expression is configured to:
create a first constraint expression of each of the partial problems by extracting a constraint expression that includes only a variable included in each of the partial problems of the constraint expression group; and
create a second constraint expression of each of the partial problems on the basis of a remaining constraint expression, excluding the first constraint expression, of the constraint expression group and the past allocation result data.

### Claim 3 (depends on 1)

The information processing device according to claim 1, wherein the determining of the division granularity is configured to:
search for a maximum problem size that is solved within the allowable time on the basis of a problem size of the linear programming problem and the allowable time; and
determine the division granularity on the basis of the searched maximum problem size.

### Claim 4 (depends on 3)

The information processing device according to claim 3, wherein the determining of the division granularity is configured to:
set units of week or month as the division granularity in a case where the problem size of the linear programming problem is determined according to the number of days.

### Claim 5 (depends on 1)

The information processing device according to claim 1, the processing further including:
outputting the solution for the linear programming problem.

### Claim 6

An information processing method implemented by a computer, the information processing method comprising:
determining a division granularity when a linear programming problem is divided into a plurality of partial problems on the basis of an allowable time needed to solve the linear programming problem to be solved;
creating an objective function of each of partial problems divided from the linear programming problem on the basis of the determined division granularity from an objective function of the linear programming problem;
creating a constraint expression of each of the partial problems on the basis of a constraint expression group of the linear programming problem and past allocation result data regarding a variable included in the linear programming problem; and
obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on the basis of the objective function and the constraint expression created for each of the partial problems.

### Claim 7

A non-transitory computer-readable storage medium storing an information processing program for causing a computer to execute processing, the processing including:
determining a division granularity when a linear programming problem is divided into a plurality of partial problems on the basis of an allowable time needed to solve the linear programming problem to be solved;
creating an objective function of each of partial problems divided from the linear programming problem on the basis of the determined division granularity from an objective function of the linear programming problem;
creating a constraint expression of each of the partial problems on the basis of a constraint expression group of the linear programming problem and past allocation result data regarding a variable included in the linear programming problem; and
obtaining a solution for the linear programming problem by sequentially solving each of the partial problems on the basis of the objective function and the constraint expression created for each of the partial problems.
