METHOD AND SYSTEM FOR SOLVING THE LAGRANGIAN DUAL OF A BINARY POLYNOMIALLY CONSTRAINED POLYNOMIAL PROGRAMMING PROBLEM USING A QUANTUM ANNEALER

摘要

A method is disclosed for solving the Lagrangian dual of a binary polynomiallyconstrained polynomial programming problem. The method comprises obtaining abinary polynomially constrained polynomial programming problem; until aconvergence is detected, iteratively, providing a set of Lagrange multipliers,providing an unconstrained binary quadratic programming problem representativeofthe Lagrangian relaxation of the binary polynomially constrained polynomialprogramming problem at these Lagrange multipliers, providing the unconstrainedbinary quadratic programming problem to a quantum annealer, obtaining from thequantum annealer at least one corresponding solution, using the at least onecorresponding solution to generate a new set of Lagrange multipliers; andprovidingall corresponding best-known primal-dual pairs and best-known feasiblesolutionsafter convergence.