Search All Applications in Quantum Computing
Application US20190391807
Published 2019-12-26
Computer-readable Recording Medium Storing Optimization Problem Computing Program And Optimization Problem Computing System
A processing unit generates a first graph that has a plurality of vertices respectively corresponding to all variables included in an objective function and has edges each connecting two vertices to indicate an existence of interaction between corresponding variables, generates a second graph, which is an abstraction of the first graph, by repeatedly merging two vertices connected by an edge into one vertex in the first graph, classifies all variables into candidates for variable groups to be respectively used for partial problems and a candidate for a boundary variable group to be used for computing a complete solution to a combinatorial optimization problem, based on the connection relationship among a plurality of vertices included in the second graph and a partition count, and determines the variable groups and boundary variable group, based on these candidates by reference to the connection relationship among the vertices included in the first graph.
Much More than Average Length Specification
View the Patent Matrix® Diagram to Explore the Claim Relationships
USPTO Full Text Publication >
- 1. A non-transitory computer-readable recording medium storing an optimization problem computing program that causes a computer to perform a process comprising:
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.
- 6. A non-transitory computer-readable recording medium storing an optimization problem computing program that causes a computer to perform a process comprising:
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 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.
- 9. An optimization problem computing system comprising:
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,
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, 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
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.
