Information processing apparatus, combination optimization method, and computer-readable recording medium recording combination optimization program

Patent metadata

Field	Value
Publication number	US-2021065087-A1
Application number	US-202016897333-A
Country	US
Kind code	A1
Filing date	Jun 10, 2020
Priority date	Aug 26, 2019
Publication date	Mar 4, 2021
Grant date	—

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.

First claim

What is claimed is:

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.

2 . 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.

3 . 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.

4 . 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.

5 . 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.

6 . 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.

7 . 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.

8 . 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.

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.

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.

Assignees

• Fujitsu Ltd

Inventors

• Oshima Hirotaka

Classifications

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06Q10/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) · CPC title