# US 2023/0267165 A1 · Computer-readable recording medium storing data processing program, data processing device, and data processing method

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

- Number: US 2023/0267165 A1
- Document ID: US20230267165A1
- Status: Published application
- Kind: A1
- Application number: 17/980,586
- Filed: 2022-11-04
- Published: 2023-08-24
- Earliest claimed: 2022-02-24
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Yasuhiro Watanabe; Hirotaka Tamura
- Web page: https://patentgrep.com/patent/US20230267165A1

## 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)}
- G06N 7/00: Computing arrangements based on specific mathematical models
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A computer-readable recording medium storing a program for causing a computer of searching for a solution for a combinatorial optimization problem represented by an energy function including state variables, to execute processing including: executing search processing of searching for the solution by performing determination whether or not to accept a change of each value of a plurality of first state variables, for the plurality of first state variables selected from among the state variables in parallel and executing processing of changing the value of one state variable of which the change of the value is determined to be accepted while changing the plurality of selected first state variables; and specifying the number of the plurality of selected first state variables, based on a search status of the search processing or search information that indicates a search record of another combinatorial optimization problem and repeating the search processing.

## Claims

### Claim 1

A non-transitory computer-readable recording medium storing a data processing program for causing a computer of searching for a solution for a combinatorial optimization problem represented by an energy function that includes a plurality of state variables, to execute processing comprising:
executing search processing of searching for the solution by performing determination whether or not to accept a change of each value of a plurality of first state variables, for the plurality of first state variables selected from among the plurality of state variables in parallel and executing processing of changing the value of one state variable of which the change of the value is determined to be accepted while changing the plurality of selected first state variables; and
specifying the number of the plurality of selected first state variables, based on a search status of the search processing or search information that indicates a search record of another combinatorial optimization problem and repeating the search processing.

### Claim 2 (depends on 1)

The non-transitory computer-readable recording medium according to claim 1, wherein the search information includes a first cumulative value in a first period, on the number of second state variables of which the change of the value is determined to be accepted, among the plurality of first state variables.

### Claim 3 (depends on 2)

The non-transitory computer-readable recording medium according to claim 2, the processing further comprising:
calculating a first average value in the first period, of the number of the second state variables, based on the first cumulative value;
reducing the number of the plurality of first state variables in a case where the first average value is larger than a first threshold; and
increasing the number of the plurality of first state variables in a case where the first average value is smaller than a second threshold that is smaller than the first threshold.

### Claim 4 (depends on 1)

The non-transitory computer-readable recording medium according to claim 1, wherein the search information includes a second cumulative value in a second period, of the number of third state variables of which the value changes, among the plurality of first state variables.

### Claim 5 (depends on 4)

The non-transitory computer-readable recording medium according to claim 4, the processing further comprising:
calculating an occurrence rate of the third state variable, in the second period, based on the second cumulative value;
reducing the number of the plurality of first state variables, in a case where the occurrence rate is larger than a third threshold; and
increasing the number of the plurality of first state variables in a case where the occurrence rate is smaller than a fourth threshold that is smaller than the third threshold.

### Claim 6 (depends on 1)

The non-transitory computer-readable recording medium according to claim 1, wherein the search information includes a movement amount represented by a Hamming distance, in a third period, of a state vector according to the plurality of state variables.

### Claim 7 (depends on 6)

The non-transitory computer-readable recording medium according to claim 6, the processing further comprising:
calculating a second average value of the movement amount, in the third period, based on the movement amount;
reducing the number of the plurality of first state variables in a case where the second average value is larger than a fifth threshold and a minimum value of the energy function is not updated in the search processing in the third period; and
increasing the number of the plurality of first state variables in a case where the second average value is smaller than a sixth threshold that is smaller than the fifth threshold and the minimum value is not updated.

### Claim 8

A data processing device of searching for a solution for a combinatorial optimization problem represented by an energy function that includes a plurality of state variables, the data processing device comprising:
a memory; and
a processor circuit coupled to the memory, the processor circuit being configured to perform processing comprising:
determining whether or not to accept a change of each value of a plurality of first state variables in parallel for the plurality of first state variables selected from among the plurality of state variables;
executing search processing of searching for the solution by executing processing of changing the value of the one state variable of which the change of the value is determined to be accepted while changing the plurality of selected first state variables;
specifying the number of the plurality of selected first state variables based on a search status of the search processing or search information that indicates a search record of another combinatorial optimization problem; and
repeating the search processing.

### Claim 9 (depends on 8)

The data processing device according to claim 8, wherein
the processor circuit includes M (M is integer equal to or more than two) modules that are grouped and a selector in n (n is integer equal to or more than two) groups each of which includes one or a plurality of modules,
the n groups make the determination regarding the plurality of first state variables in parallel, for each n replicas of a plurality of replicas that respectively indicates the plurality of state variables, for each unit processing period,
the selector selects one state variable of which the change of the value is determined to be accepted according to the determination for each of the n groups in parallel, and
the processing circuit is configured to perform control so that a group other than a first group of the n groups does not start to process a first replica, until update processing of changing the value of the state variable selected by the selector, of the first replica that is one of the plurality of replicas, ends in the first group of the n groups.

### Claim 10

A data processing method of searching for a solution for a combinatorial optimization problem represented by an energy function that includes a plurality of state variables, the data processing method comprising:
executing, by a processor circuit of a computer, search processing of searching for the solution by performing determination whether or not to accept a change of each value of a plurality of first state variables, for the plurality of first state variables selected from among the plurality of state variables in parallel and executing processing of changing the value of one state variable of which the change of the value is determined to be accepted while changing the plurality of selected first state variables; and
specifying, by the processor circuit of the computer, the number of the plurality of selected first state variables, based on a search status of the search processing or search information that indicates a search record of another combinatorial optimization problem and repeating the search processing.
