Patent US10275423

Method and system for continuous optimization using a binary sampling device
[+] Show Details

US10275423

1. A method for continuous optimization using a stochastic search process, the method comprising: (5) (4)

obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables in a digital computer;

initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in the digital computer in order to solve the optimization problem;

until a stopping criterion is met: constructing in the digital computer at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,

providing the at least one polynomial in binary variables to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing,

sampling from the domains of the at least one polynomial in binary variables using the binary sampling device to generate binary sample points,

receiving the generated binary sample points in the digital computer and transiting to next state of the stochastic search process; and

providing a best known solution found as a solution of the optimization problem using the digital computer.

2. The method as claimed in claim 1, wherein the optimization problem comprises an objective function with equality and inequality constraints. (0)

3. The method as claimed in claim 1, wherein the optimization problem is obtained in the digital computer from at least one of a user, a computer, a software package and an agent. (0)

4. The method as claimed in claim 1, wherein the initiating of a stochastic search process in the digital computer comprises: (0) (4)

5. The method as claimed in claim 1, wherein the providing of a best known solution found as a solution of the optimization problem comprises providing the best state found to a user interacting the digital computer. (0)

6. The method as claimed in claim 1, wherein the providing of a best known solution found as a solution of the optimization problem comprises providing the best known solution found to another computer operatively connected to the digital computer. (0)

7. A digital computer comprising: (0) (4)

a central processing unit;

a display device;

a communication port for operatively connecting the digital computer to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing;

a memory unit comprising an application for continuous optimization using a stochastic search process, the application comprising: instructions for obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables;

instructions for initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in order to solve the optimization problem;

instructions for, until a stopping criterion is met: constructing at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,

providing the at least one stochastically generated polynomial in binary variables to the binary sampling device via the communication port,

receiving generated binary sample points obtained by sampling from the domains of the at least one stochastically generated polynomial in binary variables using the binary sampling device and transiting to next state of the stochastic search process; and

instructions for providing a best known solution found as a solution of the optimization problem.

8. A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for continuous optimization using a stochastic search process, the method comprising: (0) (4)

obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables;

initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in order to solve the optimization problem;

until a stopping criterion is met: constructing at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,

providing the at least one stochastically generated polynomial in binary variables to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing, and

providing a best known solution found as a solution of the optimization problem.

9. A method for continuous optimization using a stochastic search process, the method comprising: (0) (4)

obtaining, in a digital computer, an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables;

initiating a stochastic search process in the digital computer in order to solve the optimization problem, wherein the stochastic search process respects a neighborhood structure of the plurality of discrete variables;

receiving, in the digital computer, generated binary sample points obtained by sampling from the domains of the at least one stochastically generated polynomial in binary variables using the binary sampling device, and

transiting to next state of the stochastic search process; and

providing a best known solution found as a solution of the optimization problem using the digital computer.

View Abstract and Specification Size

PDF with Images and Document Face >

Full Text Publication >

Patent US10275423

Method and system for continuous optimization using a binary sampling device

Patent Matrix® Search