# US 2021/0065087 A1 · Information processing apparatus, combination optimization method, and computer-readable recording medium recording combination optimization program

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

- Number: US 2021/0065087 A1
- Document ID: US20210065087A1
- Status: Published application
- Kind: A1
- Application number: 16/897,333
- Filed: 2020-06-10
- Published: 2021-03-04
- Earliest claimed: 2019-08-26
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Hirotaka Oshima
- Web page: https://patentgrep.com/patent/US20210065087A1

## CPC

- G06Q 10/06315: {Needs-based resource requirements planning or analysis}
- G06F 16/245: Query processing
- 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 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- 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)
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/047: Probabilistic or stochastic networks
- 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
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

An information processing apparatus includes: a memory; and a processor coupled to the memory and configured to: store, in the memory, values of a plurality of state variables included in a first energy function given with a term representing a constraint condition for the plurality of state variables; and performs a search for the values of the plurality of state variables which minimize a value of the first energy function, wherein the search performed by the processor includes a first search performed by using the first energy function, a second search performed by using a second energy function obtained by removing the term representing the constraint condition from the first energy function after the first search, and a third search performed by using the first energy function after the second search.

## Claims

### Claim 1

An information processing apparatus comprising:
a memory; and
a processor coupled to the memory and configured to:
store, in the memory, values of a plurality of state variables included in a first energy function given with a term representing a constraint condition for the plurality of state variables; and
performs a search for the values of the plurality of state variables which minimize a value of the first energy function,
wherein the search performed by the processor includes a first search performed by using the first energy function, a second search performed by using a second energy function obtained by removing the term representing the constraint condition from the first energy function after the first search, and a third search performed by using the first energy function after the second search.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1,
wherein the first energy function includes a parameter representing a weight of the term of a removal candidate, and
wherein the processor changes the first energy function to the second energy function by setting the parameter to zero from a value of non-zero, and changes the second energy function to the first energy function by returning the parameter to the value of non-zero from zero.

### Claim 3 (depends on 1)

The information processing apparatus according to claim 1,
wherein the first energy function includes a plurality of the terms representing the constraint condition, and
wherein the second energy function is a function obtained by removing some terms of the plurality of terms from the first energy function.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3,
wherein the processor performs the search a plurality of times, and change the term of a removal target in a certain time and another time.

### Claim 5 (depends on 1)

The information processing apparatus according to claim 1,
wherein the first energy function includes a plurality of the terms representing the constraint condition, and
wherein the second energy function is a function obtained by removing all of the plurality of terms from the first energy function.

### Claim 6 (depends on 1)

The information processing apparatus according to claim 1,
wherein the processor stochastically determines whether or not to execute the second search in a trial of state transition in the search.

### Claim 7 (depends on 1)

The information processing apparatus according to claim 1,
wherein the processor executes the second search in a case of falling into a local solution by the first search.

### Claim 8 (depends on 1)

The information processing apparatus according to claim 1,
wherein the memory stores a coupling coefficient for each set of state variables corresponding to the energy function used for the search, and
wherein the processor is configured to:
in a case where any of the values of the plurality of state variables is changed, calculate change values of energies in a case where the respective values of the plurality of state variables are set as subsequent change candidates based on the values of the plurality of state variables and the coupling coefficient stored in the memory;
change any of the values of the plurality of state variables stored in the memory based on a set temperature value, a random number value, and the change values of a plurality of the energies;
store a first coupling coefficient for each set of state variables corresponding to the first energy function in the memory, and, in a process of the search; and
change the first coupling coefficient stored in the memory to a second coupling coefficient for each set of state variables corresponding to the second energy function.

### Claim 9

A combination optimization method, in which a combination optimization apparatus performs a search for values of a plurality of state variables which minimize a value of a first energy function including the plurality of state variables and given with a term representing a constraint condition for the plurality of state variables,
wherein the search includes a first search performed by using the first energy function, a second search performed by using a second energy function obtained by removing the term representing the constraint condition from the first energy function after the first search, and a third search performed by using the first energy function after the second search.

### Claim 10

A non-transitory computer-readable recording medium recording a combination optimization program causing a computer to execute a process of performing a search for values of a plurality of state variables which minimize a value of a first energy function including the plurality of state variables and given with a term representing a constraint condition for the plurality of state variables,
wherein the search includes a first search performed by using the first energy function, a second search performed by using a second energy function obtained by removing the term representing the constraint condition from the first energy function after the first search, and a third search performed by using the first energy function after the second search.
