System and method to hardcode interger linear optimization problems on physical implementations of the Ising model

Patent metadata

Field	Value
Publication number	US-10691771-B2
Application number	US-201815920436-A
Country	US
Kind code	B2
Filing date	Mar 13, 2018
Priority date	Mar 13, 2017
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

Systems and methods for allowing analog Ising machines to be able to run Integer Linear Programming (“ILP”) problems, i.e. a compilation method for setting the state of the physical memory units, flexible to be adapted to each specific device. The method describes how variables and numeric parameters which specify the problem can be hard-coded (embedded and physically represented) in the hardware circuitry of the device in a deterministic way, with a pre-determined bound on the number of required physical spins to be used in the Ising device.

First claim

The invention claimed is:

1. A method for generating an embedding pattern used for solving an Integer Linear Programming problem using a Physical Ising Machine characterized by an hardware graph architecture comprising a plurality of blocks, each block comprising a plurality of spins, the method comprising: use of a processing device for: obtaining an indication of an ILP problem to solve using the Physical Ising Machine; wherein the ILP problem is defined using an integer encoding to binary variables, with a linear objective function and a set of inequality or equality constraints; decomposing the ILP into an ordered sequence of clusters representative of the ILP problem; selecting an ordered sequence of adjacent blocks in the hardware graph collectively mapping a subset of the spins in the selected blocks in 1-to-1 correspondence to the ILP binary variables; determining a set of auxiliary spins in each block that are associated to the variables that keep track of the total or partial weighted sum of the one or more constraints in the ILP; further wherein the determined blocks comprises a set of terminals for providing a coupling between the blocks that could be put into 1-to-1 correspondence with the duplicated auxiliary variables in each set of adjacent cluster, two-by-two; and providing an indication of the how to hard-code the embedded Ising Hamiltonian on the selected block structure;
wherein the “decomposing of the ILP problem into an ordered sequence of clusters representative of the ILP problem” comprises determining a first cluster K1 and a second cluster K2 such that the variables in each ILP inequality or equality constraints are associated either to K1 or K2, and for each ILP constraint: a new sub-constraint is created where the weighted sum of variables obtained by changing the original constraint formulation by setting all the variables not in K1 to zero, is required to sum to a value equal to an arbitrary weighted sum of newly introduced auxiliary variables, G(1); a new sub-constraint is created where the weighted sum of variables obtained by changing the original constraint formulation by setting all the variables not in K2 to zero, is required to sum to a value equal to a second arbitrary weighted sum of newly introduced auxiliary variables G(2), minus the sum defined by G′(1): a copy of the weighted sum G(1); a new sub-constraint is created where the weighted sum G(2) is copied to G′(2), another set of variables required to be subject to the original ILP constraint defined over all the variables.

2. The method as claimed in claim 1 , wherein the indication of an ILP problem is obtained from one of a user interacting with the processing device, a memory located in the processing device and a remote processing device operatively connected to the processing device.

3. The method as claimed in claim 1 , wherein a total N+2 number of clusters can be defined applying recursively the subdivision of the variables as K2 relates to K1, where only the last auxiliary variables G(N+2) are required to be subject to the original ILP constraint of all the variables.

4. The method as claimed in claim 1 , wherein “selecting an ordered sequence of adjacent blocks in the hardware graph collectively mapping a subset of the spins in the selected blocks in 1-to-1 correspondence to the ILP binary variables” comprises identifying families of disjoint, connected subgraphs in the hardware graphs for which a given minor embedding of a specific type of graph with prescribed connectivity properties is known, and for which there is at least one coupling that connects two adjacent blocks in the sequence.

5. The method as claimed in claim 4 , where the specific type of graph with a known embedding is a fully-connected, complete graph.

6. The method as claimed in claim 4 , where the specific type of graph with a known embedding is a fully-connected, complete graph of N variables united with M arbitrarily connected nodes of which a subset could be connected arbitrarily to up to N distinct variables of the complete graph.

7. The method as claimed in claim 6 , where the known embedding is provided from one of a user interacting with the processing device, a memory located in the processing device, a remote processing device operatively connected to the processing device.

8. The method as claimed in claim 4 , wherein the “determining a set of auxiliary spins in each block that are associated to the variables that keep track of the total or partial weighted sum of the one or more constraints in the ILP; further wherein the determined blocks comprises a set of terminals for providing a coupling between the blocks that could be put into 1-to-1 correspondence with the duplicated auxiliary variables in each set of adjacent cluster, two-by-two” comprises the mapping of the variables in the clusters defined in the step “decomposing the ILP into an ordered sequence of clusters representative of the ILP problem” in such a way that the associations are mapping ILP variables of cluster X in the sequence to logical embedded variables in block X in the sequence, using said known embedding, and mapping auxiliary variables in the weighted sums G(X) and G′(X) to logical embedded variables in blocks X, X+1 respectively, in such a way that there exist at least a coupling between each variable in G(X) and one variable in G′(X).

9. The method as claimed in claim 8 , wherein the “providing an indication of the how to hard-code the embedded Ising Hamiltonian on the selected block structure” comprises implementing on the Physical Ising Machine the proper physical actions that determine the values of the couplings and local fields after the hard-coding of the embedded Ising Hamiltonian, where the couplings connecting spins that belong to the same logical spins in said known embedding patterns, and said couplings that connect auxiliary variables associated in adjacent clusters can assume tunable negative values.

10. The method as claimed in claim 1 , wherein at least one of: the decomposing of the ILP problem into an ordered sequence of clusters, the selection of an ordered sequence of adjacent blocks in the hardware graph collectively mapping a subset of the spins in the selected blocks in 1-to-1 correspondence to the ILP binary variables; the determination of a set of auxiliary spins in each block that are associated to the variables that keep track of the total or partial weighted sum of the one or more constraints in the ILP; the indication of the how to hard-code the embedded Ising Hamiltonian on the selected block structure is provided to a user interacting with the processing device.

11. The method as claimed in claim 1 , wherein at least one of: the decomposing of the ILP problem into an ordered sequence of clusters, the selection of an ordered sequence of adjacent blocks in the hardware graph collectively mapping a subset of the spins in the selected blocks in 1-to-1 correspondence to the ILP binary variables; the determination of a set of auxiliary spins in each block that are associated to the variables that keep track of the total or partial weighted sum of the one or more constraints in the ILP; the indication of the how to hard-code the embedded Ising Hamiltonian on the selected block structure is stored in a memory located in the processing device and providing the indication of the embedding pattern to a remote processing device operatively connected to the processing device.

12. The method as claimed in claim 1 , wherein at least one of: the decomposing of the ILP problem into an ordered sequence of clusters, the selection of an ordered sequence of adjacent blocks in the hardware graph collectively mapping a subset of the spins in

Assignees

• Univ Space Research Association
• Univ Cornell

Inventors

• Venturelli Davide
• Trummer Immanuel

Classifications

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · 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/003

  Physics · mapped topic

• G06N10/00

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