Application US20190391807

COMPUTER-READABLE RECORDING MEDIUM STORING OPTIMIZATION PROBLEM COMPUTING PROGRAM AND OPTIMIZATION PROBLEM COMPUTING SYSTEM
[+] Show Details

US20190391807

1. A non-transitory computer-readable recording medium storing an optimization problem computing program that causes a computer to perform a process comprising: (4) (10)

obtaining a coefficient value set indicating strength of interactions between variables included in an objective function and a partition count to be used for partitioning a combinatorial optimization problem into a plurality of partial problems, the objective function being an Ising objective function obtained by transforming the combinatorial optimization problem;

generating, based on the coefficient value set, a first graph that includes a plurality of first vertices respectively corresponding to all the variables included in the objective function and edges each connecting two of the plurality of first vertices, in such a way that an existence or absence of each of the edges indicates an existence or absence of an interaction between variables corresponding to first vertices connected by said each edge;

generating a second graph by repeatedly merging two first vertices connected by one of the edges among the plurality of first vertices into one vertex in the first graph, the second graph being an abstraction of the first graph;

classifying, based on connection relationship among a plurality of second vertices included in the second graph and the partition count, all the variables into candidate variable groups for variable groups and a candidate boundary variable group for a boundary variable group, the variable groups being respectively used for the plurality of partial problems, the boundary variable group being used for computing a complete solution of the combinatorial optimization problem, based on solutions to the plurality of partial problems;

determining the variable groups and the boundary variable group, based on the candidate variable groups and the candidate boundary variable group by reference to connection relationship among the plurality of first vertices included in the first graph;

setting a fixed value for the boundary variable group;

individually sending, with respect to each of the plurality of partial problems, a coefficient value subset that includes a correction value calculated based on the fixed value and indicates strength of interactions between variables belonging to a corresponding one of the variable groups, to an Ising machine;

receiving values of the variable groups respectively indicating the solutions to the plurality of partial problems from the Ising machine;

computing a value of the objective function, based on the values of the variable groups, the fixed value set for the boundary variable group, and the coefficient value set; and

repeating change of the fixed value, the sending of a coefficient value subset with respect to said each partial problem to the Ising machine, the receiving of values of the variable groups, and the computing of a value of the objective function until a convergence condition is satisfied, and outputting, upon detecting that the convergence condition is satisfied, values of all the variables that minimize the objective function.

2. The non-transitory computer-readable recording medium according to claim 1, wherein: (0) (2)

3. The non-transitory computer-readable recording medium according to claim 1, wherein the process further includes, upon detecting that connection destination vertices of a first vertex corresponding to a first variable belonging to the candidate boundary variable group in the first graph are each either a vertex corresponding to another variable belonging to the candidate boundary variable group or a vertex corresponding to a second variable belonging to a first variable group that is one of the candidate variable groups, determining to set the first variable so as to belong to the first variable group. (0)

4. The non-transitory computer-readable recording medium according to claim 1, wherein the merging includes preferentially merging, into the one vertex, the two first vertices that have fewer edges connected thereto than other first vertices among the plurality of first vertices. (0)

5. The non-transitory computer-readable recording medium according to claim 1, wherein the process further includes: (0) (4)

selecting, based on values of the coefficient value subset, an invalid variable from the corresponding one of the variable groups, the invalid variable being a variable for which a value that lowers the value of the objective function is determined by itself;

setting the invalid variable to the value that lowers the value of the objective function;

updating the correction value, based on the value of the invalid variable; and

generating a new coefficient value subset that includes the updated correction value and indicates strength of interactions between variables belonging to a group of valid variables, excluding the invalid variable, in the corresponding one of the variable groups.

6. A non-transitory computer-readable recording medium storing an optimization problem computing program that causes a computer to perform a process comprising: (2) (10)

setting M patterns (M is a natural number of two or greater) of fixed value, which are different from each other, for the boundary variable group;

individually sending, with respect to each of the plurality of partial problems, M patterns of coefficient value subset which each include a correction value calculated based on one of the M patterns of fixed value and indicate strength of interactions between variables belonging to a corresponding one of the variable groups, respectively to M Ising machines;

receiving values of the variable groups respectively indicating the solutions to the plurality of partial problems from each of the M Ising machines;

computing M patterns of value of the objective function, based on the values of the variable groups, the M patterns of fixed value set for the boundary variable group, and the coefficient value set; and

repeating generation of new M patterns of fixed value, the sending of M patterns of coefficient value subset with respect to said each partial problem to the M Ising machines, the receiving of values of the variable groups, and the computing of M patterns of value of the objective function until a convergence condition is satisfied, and outputting, upon detecting that the convergence condition is satisfied, values of all the variables that minimize the objective function.

7. The non-transitory computer-readable recording medium according to claim 6, wherein the new M patterns of fixed value are generated by flipping a value at one bit position, which is different for each of the new M patterns, in a fixed value used for obtaining a minimum value among the computed M patterns of value of the objective function. (0)

8. The non-transitory computer-readable recording medium according to claim 6, wherein the new M patterns of fixed value are generated based on M patterns of fixed value used for obtaining M patterns of value of the objective function that are selected in increasing order of value of the objective function from among currently computed M patterns of value of the objective function and last computed M patterns of value of the objective function. (0)

9. An optimization problem computing system comprising: (0) (2)

an Ising machine configured to perform a first process including receiving coefficient value subsets respectively corresponding to a plurality of partial problems into which a combinatorial optimization problem is partitioned, in a coefficient value set, the coefficient value subsets each including part of the coefficient value set, the coefficient value set indicating strength of interactions between variables included in an objective function, the objective function being an Ising objective function obtained by transforming the combinatorial optimization problem, and

solving the plurality of partial problems, based on the coefficient value subsets; and

an information processing apparatus configured to perform a second process including obtaining the coefficient value set and a partition count to be used for partitioning the combinatorial optimization problem into the plurality of partial problems,

setting a fixed value for the boundary variable group,

individually sending, with respect to each of the plurality of partial problems, one of the coefficient value subsets that each include a correction value calculated based on the fixed value and indicate strength of interactions between variables belonging to a corresponding one of the variable groups, to the Ising machine,

receiving values of the variable groups respectively indicating the solutions to the plurality of partial problems from the Ising machine,

computing a value of the objective function, based on the values of the variable groups, the fixed value set for the boundary variable group, and the coefficient value set, and

View Abstract and Specification Size

PDF with Images and Document Face >

Full Text Publication >

Application US20190391807

COMPUTER-READABLE RECORDING MEDIUM STORING OPTIMIZATION PROBLEM COMPUTING PROGRAM AND OPTIMIZATION PROBLEM COMPUTING SYSTEM

Patent Matrix® Search