Computer-readable recording medium storing optimization problem computing program and optimization problem computing system

Patent metadata

Field	Value
Publication number	US-2019391807-A1
Application number	US-201916434375-A
Country	US
Kind code	A1
Filing date	Jun 7, 2019
Priority date	Jun 20, 2018
Publication date	Dec 26, 2019
Grant date	—

Abstract

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.

First claim

What is claimed is:

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.

2 . The non-transitory computer-readable recording medium according to claim 1 , wherein:
each variable included in the variable groups has interactions only with other variables included in one of the variable groups to which said each variable belongs or variables included in the boundary variable group; and each variable included in the boundary variable group has interactions with variables included in two or more of the variable groups.

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.

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.

5 . The non-transitory computer-readable recording medium according to claim 1 , wherein the process further includes:
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:
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 var

Assignees

• Fujitsu Ltd

Inventors

• Inagaki Kazuhisa
• Sakai Akira

Classifications

• 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

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

• G06F9/223 Primary

  Execution means for microinstructions irrespective of the microinstruction function, e.g. decoding of microinstructions and nanoinstructions; timing of microinstructions; programmable logic arrays; delays and fan-out problems · CPC title

• G06N10/00

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title