Data processing apparatus and data processing method

Patent metadata

Field	Value
Publication number	US-2024111833-A1
Application number	US-202318372413-A
Country	US
Kind code	A1
Filing date	Sep 25, 2023
Priority date	Sep 28, 2022
Publication date	Apr 4, 2024
Grant date	—

Abstract

A storing unit stores, amongst coefficients, values of a coefficient group associated with one selected from multiple variable groups, which are obtained by dividing state variables of an evaluation function. A searching unit searches for a solution to an optimization problem by repeating update processing, which includes calculating, using the values of the coefficient group, a value change of the evaluation function responsive to changing the value of each state variable of the variable group and changing the value of one state variable thereof based on the value change and temperature. A processing unit calculates multiplicity indicating the iteration count in which the values of the variable group are maintained in a search using Markov chain Monte Carlo (MCMC), and causes, responsive to cumulated multiplicity exceeding a threshold, the searching unit to perform the update processing using the values of the coefficient group associated with a different variable group.

First claim

What is claimed is:

1 . A data processing apparatus comprising:
a first memory configured to store values of a plurality of weight coefficients included in an evaluation function which is obtained by transforming a combinatorial optimization problem; a second memory configured to store, amongst the plurality of weight coefficients, values of a weight coefficient group which is associated with a state variable group selected from a plurality of state variable groups, the plurality of state variable groups being obtained by dividing a plurality of state variables included in the evaluation function; a searching circuit configured to search for a solution to the combinatorial optimization problem by repeating an update process, the update process including a process of calculating, using the values of the weight coefficient group read from the second memory, a change in a value of the evaluation function responsive to changing a value of each of state variables of the state variable group and a process of changing a value of one of the state variables of the state variable group based on the change and a temperature value; and a processing circuit configured to calculate, based on the change and the temperature value, multiplicity indicating a number of iterations in which the values of the state variables of the state variable group are maintained in searching for the solution using a Markov chain Monte Carlo method, and cause, responsive to a cumulated value of the multiplicity exceeding a predetermined threshold, the searching circuit to perform the update process using the values of the weight coefficient group which is associated with a different state variable group selected from the plurality of state variable groups.

2 . The data processing apparatus according to claim 1 , wherein:
the searching circuit outputs values of the plurality of state variables for each of the update processes, and the processing circuit outputs the multiplicity for each state formed by the values of the plurality of state variables.

3 . The data processing apparatus according to claim 1 , wherein:
the processing circuit calculates, for each of the state variables of the state variable group, an acceptance probability of accepting a value change based on the change and the temperature value, calculates an escape probability by dividing a sum of the acceptance probability calculated for the each of the state variables of the state variable group by a number of the state variables of the state variable group, and calculates the multiplicity based on the escape probability and a random number value.

4 . The data processing apparatus according to claim 3 , wherein:
the processing circuit calculates the acceptance probability by shift operation.

5 . The data processing apparatus according to claim 1 , wherein:
the second memory includes a first storage area and a second storage area, and while the searching circuit is performing the update process using the values of the weight coefficient group stored in the first storage area, the values of the weight coefficient group associated with the different state variable group are read from the first memory and written to the second storage area.

6 . A non-transitory computer-readable recording medium storing therein a computer program that causes a computer to execute a process comprising:
storing, in a first memory, values of a plurality of weight coefficients included in an evaluation function which is obtained by transforming a combinatorial optimization problem; storing, in a second memory, amongst the plurality of weight coefficients, values of a weight coefficient group which is associated with a state variable group selected from a plurality of state variable groups, the plurality of state variable groups being obtained by dividing a plurality of state variables included in the evaluation function; searching for a solution to the combinatorial optimization problem by repeating an update process, the update process including a process of calculating, using the values of the weight coefficient group read from the second memory, a change in a value of the evaluation function responsive to changing a value of each of state variables of the state variable group and a process of changing a value of one of the state variables of the state variable group based on the change and a temperature value; calculating, based on the change and the temperature value, multiplicity indicating a number of iterations in which the values of the state variables of the state variable group are maintained in searching for the solution using a Markov chain Monte Carlo method; and performing, responsive to a cumulated value of the multiplicity exceeding a predetermined threshold, the update process using the values of the weight coefficient group which is associated with a different state variable group selected from the plurality of state variable groups.

7 . A data processing method comprising:
storing, by a first memory, values of a plurality of weight coefficients included in an evaluation function which is obtained by transforming a combinatorial optimization problem; storing, by a second memory, amongst the plurality of weight coefficients, values of a weight coefficient group which is associated with a state variable group selected from a plurality of state variable groups, the plurality of state variable groups being obtained by dividing a plurality of state variables included in the evaluation function; searching, by a searching circuit, for a solution to the combinatorial optimization problem by repeating an update process, the update process including a process of calculating, using the values of the weight coefficient group read from the second memory, a change in a value of the evaluation function responsive to changing a value of each of state variables of the state variable group and a process of changing a value of one of the state variables of the state variable group based on the change and a temperature value; calculating, by a processing circuit, based on the change and the temperature value, multiplicity indicating a number of iterations in which the values of the state variables of the state variable group are maintained in searching for the solution using a Markov chain Monte Carlo method, and causing, responsive to a cumulated value of the multiplicity exceeding a predetermined threshold, the searching circuit to perform the update process using the values of the weight coefficient group which is associated with a different state variable group selected from the plurality of state variable groups.

Assignees

• Fujitsu Ltd
• Governing Council Univ Toronto

Inventors

• Chen Sigeng
• Rosenthal Jeffrey Seth
• Sheikholeslamii Ali
• Tamura Hirotaka
• Dote Aki

Classifications

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting 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

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

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