Method and system for setting parameters of a discrete optimization problem embedded to an optimization solver and solving the embedded discrete optimization problem

1. A method for setting parameters of a discrete optimization problem embedded to an optimization solver hardware and solving the embedded discrete optimization problem using the optimization solver hardware, the method comprising:

use of a processing unit for:

receiving an indication of a discrete optimization problem and a corresponding embedded graph G emb into an optimization solver hardware graph;

converting the discrete optimization problem to a K-spin problem, wherein the K-spin problem is defined as:

min

⁢

⁢

H

K

⁢

-

⁢

spin

=

∑

j

=

1

N

⁢

h

j

⁢

s

j

+

∑

k

=

2

K

⁢

∑

j

1

⁢

j

2

⁢

⁢

…

⁢

⁢

j

k

⁢

J

j

1

⁢

j

2

⁢

…

⁢

⁢

j

k

⁢

s

j

1

⁢

s

j

2

⁢

⁢

⁢

…

⁢

⁢

s

j

k

wherein parameter K is the order of the discrete optimization problem, parameter J is a coupling value between two vertices, parameter h is a local field value, s j is the jth variable of a K-spin problem which can take a value from {−1, +1}, J j1j2 . . . jk denotes the magnitude of a kth order interaction and s j1 s j2 . . . s jk represents a kth order interaction between variable j 1 j 2 and j k ;

for each variable j of the K-spin problem associated with a corresponding node:

computing a parameter C j associated with the local field and the coupling values of each adjacent edge to the corresponding node,

evaluating if a variable selection criterion is met with the computed parameter C j ,

if the variable selection criterion is met with the computed parameter C j :

setting a value of a selected variable j to a given fixed value,

adding the selected variable j with the given fixed value to a partial solution list, and

removing the selected variable from the K-spin problem and from the corresponding embedded graph to thereby provide a reduced K-spin problem and a corresponding reduced embedded graph, the corresponding reduced embedded graph comprising a plurality of edges and vertices;

setting the parameter J of each edge of the reduced embedded graph corresponding to an existing edge in the corresponding reduced K-spin problem by distributing the parameter J in the reduced K-spin problem according to a defined distributing strategy;

setting the parameter h of each given vertex of the reduced embedded graph by distributing the corresponding parameter h in the reduced K-spin problem using a linear combination of a corresponding parameter C for the given vertex and the parameter J of each edge of the corresponding variable in the reduced K-spin problem adjacent to the given vertex;

setting the parameter J of each edge of the reduced embedded graph connecting two vertices representing the same corresponding variable in the reduced K-spin problem using a distribution of the parameter C of the corresponding variable in the reduced K-spin problem calculated previously;

solving the reduced K-spin problem with the optimization solver hardware using the corresponding reduced embedded graph and its corresponding h and J parameters to provide at least one solution;

combining the at least one solution obtained from the optimization solver hardware with the partial solution list to thereby provide a solution to the discrete optimization problem; and

wherein the optimization solver hardware is a quantum annealer.

2. The method as claimed in claim 1 , wherein the discrete optimization problem is formulated as a quadratic optimization problem.

3. The method as claimed in claim 1 , wherein the discrete optimization problem is formulated as a 2-spin problem.

4. The method as claimed in claim 1 , wherein the indication of a discrete optimization problem and the corresponding embedded graph G emb into the optimization solver hardware graph are obtained from one of a user interacting with the processing unit, a memory unit operatively connected to the processing unit and a remote processing device operatively connected to the processing unit.

5. The method as claimed in claim 1 , wherein the parameter C j is defined as

C

j

=

∑

i

∈

lnbr

⁡

(

j

)

⁢



J

ji



-



h

j



,

wherein lnbr(j) is a set of neighboring vertices which includes all vertices that are connected to variable j by edges or hyperedges.

6. The method as claimed in claim 1 , wherein the evaluating if a variable selection criterion is met with the computed parameter C j comprises determining if the computed parameter C j is negative.

7. The method as claimed in claim 1 , wherein the defined distributing strategy comprises equally distributing the parameter j in the reduced K-spin problem.

8. A digital computer for setting parameters of a discrete optimization problem embedded to an optimization solver hardware and solving the embedded discrete optimization problem using the optimization solver hardware, the digital computer comprising:

a central processing unit;

a display device;

a communication port;

a memory unit comprising an application for setting parameters of a discrete optimization problem embedded to the optimization solver hardware and solving the embedded discrete optimization problem using the optimization solver hardware, the application comprising:

instructions for receiving an indication of a discrete optimization problem and a corresponding embedded graph G emb into an optimization solver hardware graph;

instructions for converting the discrete optimization problem to a K-spin problem, wherein the K-spin problem is defined as:

min

⁢

⁢

H

K

⁢

-

⁢

spin

=

∑

j

=

1

N

⁢

h

j

⁢

s

j

+

∑

k

=

2

K

⁢

∑

j

1

⁢

j

2

⁢

⁢

…

⁢

⁢

j

k

⁢

J

j

1

⁢

j

2

⁢

…

⁢

⁢

j

k

⁢

s

j

1

⁢

s

j

2

⁢

⁢

⁢

…

⁢

⁢

s

j

k

wherein parameter K is the order of the discrete optimization problem, parameter J is a coupling value between two vertices, parameter h is a local field value, s j is the jth variable of a K-spin problem which can take a value from {−1, +1}, J j1j2 . . . jk denotes the magnitude of a kth order interaction and s j1 s j2 . . . s jk represents a kth order interaction between variable j 1 j 2 and j k ;

instructions for, for each variable j of the K-spin problem associated with a corresponding node,

computing a parameter C j associated with the local field and the coupling values of each adjacent edge to the corresponding node,

evaluating if a variable selection criterion is met with the computed parameter C j ,

if the variable selection criterion is met:

setting a value of a selected variable j to a given fixed value,

adding the selected variable j with the given fixed value to a partial solution list, and

removing the selected variable from the K-spin problem and from the corresponding embedded graph to thereby provide a reduced K-spin problem and a corresponding reduced embedded graph, the corresponding reduced embedded graph comprising a plurality of edges and vertices;

instructions for setting the parameter J of each edge of the reduced embedded graph corresponding to an existing edge in the corresponding reduced K-spin problem by distributing the parameter J in the reduced K-spin problem according to a defined distributing strategy;

instructions for setting the parameter h of each given vertex of the reduced embedded graph by distributing the corresponding parameter h in the reduced K-spin problem using a linear combination of a corresponding parameter C for the given vertex and the parameter J of each edge of the corresponding variable in the reduced K-spin problem adjacent to the given vertex;

instructions for setting the parameter J of each edge of the reduced embedded graph connecting two vertices representing the same corresponding variable in the reduced K-spin problem using a distribution of the parameter C of the corresponding variable in the reduced K-spin problem calculated previously;

instructions for solving the reduced K-spin problem with the optimization solver hardware using the corresponding reduced embedded graph and its corresponding h and parameters to provide at least one solution; and

instructions for combining the at least one solution obtained from the optimization solver hardware with the partial solution list to thereby provide a solution to the discrete optimization problem;

a data bus for interconnecting the central processing unit, the display device, the communication port and the memory unit; and

wherein the optimization solver hardware is a quantum annealer.

9. A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for setting parameters of a discrete optimization problem embedded to an optimization solver hardware and solving the embedded discrete optimization problem using the optimization solver hardware, the method comprising:

use of a processing unit for:

receiving an indication of a discrete optimization problem and a corresponding embedded graph G emb into an optimization solver hardware graph;

converting the discrete optimization problem to a K-spin problem, wherein the K-spin problem is defined as:

min

⁢

⁢

H

K

⁢

-

⁢

spin

=

∑

j

=

1

N

⁢

h

j

⁢

s

j

+

∑

k

=

2

K

⁢

∑

j

1

⁢

j

2

⁢

⁢

…

⁢

⁢

j

k

⁢

J

j

1

⁢

j

2

⁢

…

⁢

⁢

j

k

⁢

s

j

1

⁢

s

j

2

⁢

⁢

⁢

…

⁢

⁢

s

j

k

wherein parameter K is the order of the discrete optimization problem, parameter J is a coupling value between two vertices, parameter h is a local field value, s j is the jth variable of a K-spin problem which can take a value from {−1, +1}, J j1j2 . . . jk denotes the magnitude of a kth order interaction and s j1 s j2 . . . s jk represents a kth order interaction between variable j 1 j 2 and j k ;

for each variable j of the K-spin problem associated with a corresponding node:

computing a parameter C j associated with the local field and the coupling values of each adjacent edge to the corresponding node,

evaluating if a variable selection criterion is met with the computed parameter C j ,

if the variable selection criterion is met:

setting a value of a selected variable j to a given fixed value,

adding the selected variable j with the given fixed value to a partial solution list, and

removing the selected variable from the K-spin problem and from the corresponding embedded graph to thereby provide a reduced K-spin problem and a corresponding reduced embedded graph, the corresponding reduced embedded graph comprising a plurality of edges and vertices;

setting the parameter J of each edge of the reduced embedded graph corresponding to an existing edge in the corresponding reduced K-spin problem by distributing the parameter J in the reduced K-spin problem according to a defined distributing strategy;

setting the parameter h of each given vertex of the reduced embedded graph by distributing the corresponding parameter h in the reduced K-spin problem using a linear combination of a corresponding parameter C for the given vertex and the parameter J of each edge of the corresponding variable in the reduced K-spin problem adjacent to the given vertex;

setting the parameter J of each edge of the reduced embedded graph connecting two vertices representing the same corresponding variable in the reduced K-spin problem using a distribution of the parameter C of the corresponding variable in the reduced K-spin problem calculated previously;

solving the reduced K-spin problem with the optimization solver hardware using the corresponding reduced embedded graph and its corresponding h and J parameters to provide at least one solution;

combining the at least one solution obtained from the optimization solver hardware with the partial solution list to thereby provide a solution to the discrete optimization problem; and

wherein the optimization solver hardware is a quantum annealer.