Solution system, solution method, and solution program

Patent metadata

Field	Value
Publication number	US-2022335323-A1
Application number	US-201917642332-A
Country	US
Kind code	A1
Filing date	Sep 24, 2019
Priority date	Sep 24, 2019
Publication date	Oct 20, 2022
Grant date	—

Abstract

Provided is a solution system capable of reducing the amount of computation when solving a combinatorial optimization problem by applying an energy function in a model representing a state of individual spins by a first value or a second value to simulated annealing. The input unit 2 receives input of an energy function in a model representing states of individual spins by a first value or a second value, wherein the energy function is corresponding to a combinatorial optimization problem to be solved. In a process of the simulated annealing, the simulated annealing unit 3 selects a spin, selects a set to which the spin belongs, and changes the states of one or more spins including the spin while a condition where the set satisfies a constraint is maintained, when the set satisfies the predetermined constraint and the state of the spin is determined to be changed.

First claim

What is claimed is:

1 . A solution system comprising:
an input unit that receives input of an energy function in a model representing states of individual spins by a first value or a second value, wherein the energy function is corresponding to a combinatorial optimization problem to be solved; and a simulated annealing unit that obtains a state of each spin corresponding to a solution of the combinatorial optimization problem by performing simulated annealing when the energy function is input, wherein, in a process of the simulated annealing, the simulated annealing unit selects a spin, selects a set to which the selected spin belongs, and changes the states of one or more spins including the selected spin while a condition where the set satisfies a constraint is maintained, when the set satisfies the predetermined constraint and the state of the spin is determined to be changed.

2 . The solution system according to claim 1 ,
as the constraint to be satisfied by the set, a constraint that only one spin among a plurality of spins belonging to the set takes the first value is defined.

3 . The solution system according to claim 1 ,
as the constraint to be satisfied by the set, a constraint that at least one spin among a plurality of spins belonging to the set takes the second value is defined.

4 . The solution system according to claim 1 ,
as the constraint to be satisfied by the set, a constraint that at least one spin among a plurality of spins belonging to the set takes the first value is defined.

5 . The solution system according to claim 1 ,
if the energy function is input, wherein the energy function is obtained by converting an expression representing energy whose order of variables representing the states of spins is reduced to second order, wherein the expression is obtained, in case order of the variables representing the states of spins of an expression representing the energy in the combinatorial optimization problem is third order or higher, by replacing a plurality of the variables representing the states of spins with a single variable to reduce the order to second order, for the set containing an auxiliary spin corresponding to the single variable after replacement and a plurality of spins corresponding to the plurality of the variables before the replacement, a constraint that the state of the auxiliary spin is changed according to the change of the any spin in the plurality of spins is defined.

6 . The solution system according to claim 1 ,
for a predetermined spin, the first value of the second value is defined as a fixed value.

7 . A solution method comprising:
receiving input of an energy function in a model representing states of individual spins by a first value or a second value, wherein the energy function is corresponding to a combinatorial optimization problem to be solved; and obtaining a state of each spin corresponding to a solution of the combinatorial optimization problem by performing simulated annealing when the energy function is input, a process of the simulated annealing comprising: selecting a spin, selecting a set to which the selected spin belongs, and changing the states of one or more spins including the selected spin while a condition where the set satisfies a constraint is maintained, when the set satisfies the predetermined constraint and the state of the spin is determined to be changed.

8 . A non-transitory computer-readable recording medium in which a solution program is recorded, the solution program to be installed in a computer that comprises an input unit that receives input of an energy function in a model representing states of individual spins by a first value or a second value, wherein the energy function is corresponding to a combinatorial optimization problem to be solved, the solution program causing the computer to perform:
a simulated annealing processing of obtaining a state of each spin corresponding to a solution of the combinatorial optimization problem by performing simulated annealing when the energy function is input, wherein the solution program causes the computer to perform, in a process of the simulated annealing, selecting a spin, selecting a set to which the selected spin belongs, and changing the states of one or more spins including the selected spin while a condition where the set satisfies a constraint is maintained, when the set satisfies the predetermined constraint and the state of the spin is determined to be changed.

Assignees

• Nec Corp

Inventors

• Takano Fumiyo
• Chishima Hiroshi

Classifications

• 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

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · 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

• G06N5/01 Primary

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