Method and system for solving the lagrangian dual of a constrained binary quadratic programming problem using a quantum annealer

Abstract

A method is disclosed for solving the Lagrangian dual of a constrained binary quadratic programming problem. The method comprises obtaining a constrained quadratic binary programming problem; until a convergence is detected, iteratively, performing a Lagrangian relaxation of the constrained quadratic binary programming problem to provide an unconstrained quadratic binary programming problem, providing the unconstrained quadratic binary programming problem to a quantum annealer, obtaining from the quantum annealer at least one corresponding solution, using the at least one corresponding solution to generate a new approximation for the Lagrangian dual bound; and providing a corresponding solution to the Lagrangian dual of the constrained binary quadratic programming problem after convergence.

1 . A method for solving the Lagrangian dual of a constrained binary quadratic programming problem, the method comprising:
 use of a processor for obtaining a constrained quadratic binary programming problem;   until a convergence is detected, use of a processor for iteratively:
 performing a Lagrangian relaxation of the constrained quadratic binary programming problem to provide an unconstrained quadratic binary programming problem; 
 providing the unconstrained quadratic binary programming problem to a quantum annealer; 
 obtaining from the quantum annealer at least one corresponding solution; 
 using the at least one corresponding solution to generate a new approximation for a Lagrangian dual bound; 
   use of a processor for providing a corresponding solution to the Lagrangian dual of the constrained binary quadratic programming problem after the convergence.   
     
     
         2 . The method as claimed in  claim 1 , wherein the use of a processor for obtaining of a constrained quadratic binary programming problem comprises:
 use of a processor for obtaining data representative of an objective function ƒ(x) having a degree less than or equal to two;   use of a processor for obtaining data representative of equality constraints having a degree less than or equal to two; and   use of a processor for obtaining data representative of inequality constraints having a degree less than or equal to two.   
     
     
         3 . The method as claimed in  claim 1 , wherein the use of a processor for obtaining the constrained quadratic binary programming problem comprises use of a processor for obtaining the constrained quadratic binary programming problem from at least one of a user, a computer, a software package and an intelligent agent. 
     
     
         4 . The method as claimed in  claim 1 , wherein the use of a processor for obtaining of the constrained quadratic binary programming problem further comprises use of a processor for initializing software parameters and use of a processor for initializing a linear programming procedure. 
     
     
         5 . The method as claimed in  claim 4 , wherein the software parameters are obtained by the processor from at least one of a user, a computer, a software package and an intelligent agent. 
     
     
         6 . The method as claimed in  claim 4 , wherein the use of a processor for initializing of the software parameters comprises:
 use of a processor for providing an embedding of the constrained quadratic binary programming problem on the quantum annealer;   use of a processor for providing an embedding solver function for providing a list of solutions;   use of a processor for providing one of lower and upper bounds and default values for Lagrange multipliers;   use of a processor for providing one of initial values and default values for Lagrange multipliers; and   use of a processor for providing an error tolerance value for duality gap.   
     
     
         7 . The method as claimed in  claim 4 , wherein the linear programming procedure is carried out until the convergence is detected. 
     
     
         8 . The method as claimed in  claim 7 , wherein the using of the at least one corresponding solution to generate a new approximation for the Lagrangian dual bound comprises using the at least one corresponding solution in the linear programming procedure. 
     
     
         9 . The method as claimed in  claim 1 , wherein the use of a processor for providing of a corresponding solution to the Lagrangian dual of the constrained binary quadratic programming problem comprises storing the corresponding solution to a file. 
     
     
         10 . A digital computer comprising:
 a central processing unit;   a display device;   a communication port for operatively connecting the digital computer to a quantum annealer;   a memory unit comprising an application for solving the Lagrangian dual of a constrained binary quadratic problem, the application comprising:
 instructions for obtaining a constrained binary quadratic problem; 
 instructions for iteratively performing a Lagrangian relaxation of the constrained quadratic problem to provide an unconstrained quadratic programming problem; 
 instructions for providing the unconstrained quadratic programming problem to the quantum annealer using the communication port; 
 instructions for obtaining from the quantum annealer via the communication port at least one corresponding solution and for using the at least one corresponding solution to generate a new approximation for a Lagrangian dual bound; 
 instructions for providing a corresponding solution to the Lagrangian dual of the constrained binary quadratic programming problem once a convergence is detected; and 
   a data bus for interconnecting the central processing unit, the display device, the communication port and the memory unit.   
     
     
         11 . A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for solving the Lagrangian dual of a constrained binary quadratic programming problem, the method comprising obtaining a constrained quadratic binary programming problem; until a convergence is detected, iteratively: performing a Lagrangian relaxation of the constrained quadratic binary programming problem to provide an unconstrained quadratic binary programming problem; providing the unconstrained quadratic binary programming problem to a quantum annealer; obtaining from the quantum annealer at least one corresponding solution; using the at least one corresponding solution to generate a new approximation for a Lagrangian dual bound and providing a corresponding solution to the Lagrangian dual of the constrained binary quadratic programming problem causing the convergence. 
     
     
         12 . Use of the method claimed in  claim 1  for solving a maximum weighted k-clique problem.