Quantum computing-enhanced systems and methods for large-scale constrained optimization

Abstract

Technologies for a quantum/classical hybrid approach to solving optimization problems are disclosed. In the illustrative embodiment, an optimization problem is decomposed into two sub-problems. The first sub-problem is solved on a classical computer, and a result from the first sub-problem is provided to a quantum computer. The quantum computer then solves the second sub-problem based on the result of the first sub-problem from the classical computer. The quantum computer can then provide a result to the classical computer to re-solve the first problem. The iterative calculation is continued until an end condition is met.

What is claimed is: 
     
         1 . An apparatus comprising:
 at least one processing device comprising a processor coupled to a memory;   the at least one processing device being configured:
 to identify an optimization problem; 
 to decompose the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables; 
 to perform two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and 
 to determine a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations; 
   wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and   wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device.   
     
     
         2 . The apparatus of  claim 1  wherein the two or more iterations are performed until at least one designated end condition is reached. 
     
     
         3 . The apparatus of  claim 2  wherein the at least one designated end condition comprises determining that a number of the two or more iterations which have been performed exceeds a designated iteration threshold. 
     
     
         4 . The apparatus of  claim 2  wherein the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on at least one of:
 a gap between a solution for the first sub-problem and a solution for the second sub-problem for a most recently completed one of the two or more iterations; and 
 a gap between a first data value derived from the solution for the first sub-problem and a second data value derived from the solution for the second sub-problem for the most recently completed one of the two or more iterations. 
 
     
     
         5 . The apparatus of  claim 2  wherein the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on determining that an improvement of at least one of a solution for the first sub-problem and a solution for the second sub-problem in a designated number of most recently completed ones of the two or more iterations is less than a designated improvement threshold. 
     
     
         6 . The apparatus of  claim 1  wherein the at least one processing device is implemented at least in part internally to at least one of the classical computing device and the quantum computing device. 
     
     
         7 . The apparatus of  claim 1  wherein, in at least a given one of the two or more iterations:
 said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device is utilized as a parameter for the first sub-problem; and 
 said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device is utilized as a parameter for the second sub-problem. 
 
     
     
         8 . The apparatus of  claim 1  wherein decomposing the identified optimization problem into the two or more sub-problems comprises decomposing the identified optimization problem such that:
 the first subset of the plurality of variables associated with the first sub-problem to be solved by the classical computing device comprises more continuous variables than discrete variables; and 
 the second subset of the plurality of variables associated with the second sub-problem to be solved by the quantum computing device comprises one of (i) more discrete variables than continuous variables and (ii) all discrete variables and no continuous variables. 
 
     
     
         9 . The apparatus of  claim 1  wherein:
 said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and 
 said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem. 
 
     
     
         10 . The apparatus of  claim 1  wherein at least one of (i) said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and (ii) said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem. 
     
     
         11 . The apparatus of  claim 1  wherein the optimization problem comprises a job scheduling problem, and wherein the first algorithm comprises a relaxed mixed-integer linear programming (MILP) solver configured to solve a MILP problem. 
     
     
         12 . The apparatus of  claim 1  wherein the optimization problem comprises a manufacturing problem, and wherein the first algorithm comprises a dual linear programming (LP) solver configured to solve a LP problem. 
     
     
         13 . The apparatus of  claim 1  wherein the optimization problem comprises a vehicle routing problem, and wherein the first algorithm comprises an operation for assigning a value to a parameter of an integer quadratic fractional program (IQFP) problem. 
     
     
         14 . The apparatus of  claim 1  wherein the second algorithm comprises a quadratic unconstrained binary optimization (QUBO) problem solver. 
     
     
         15 . A method comprising:
 identifying an optimization problem;   decomposing the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables;   performing two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and   determining a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations;   wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and   wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device; and   wherein the method is performed by at least one processing device comprising a processor coupled to a memory.   
     
     
         16 . The method of  claim 15  wherein:
 said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and 
 said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem. 
 
     
     
         17 . The method of  claim 15  wherein at least one of (i) said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and (ii) said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem. 
     
     
         18 . A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code, when executed by at least one processing device comprising a processor coupled to a memory, causes the at least one processing device:
 to identify an optimization problem;   to decompose the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables;   to perform two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and   to determine a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations;   wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and   wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device.   
     
     
         19 . The computer program product of  claim 18  wherein:
 said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and 
 said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem. 
 
     
     
         20 . The computer program product of  claim 18  wherein at least one of said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem.