Method and system for solving Lagrangian duals of a binary polynomial constrained polynomial programming problem using a binary optimizer

摘要

A method and system are disclosed for solving the Lagrangian dual of a binary polynomially constrained polynomial programming problem. The method comprises obtaining a binary polynomially constrained polynomial programming problem; until a convergence is detected, iteratively, providing a set of Lagrange multipliers, providing an unconstrained binary quadratic programming problem representative of the Lagrangian relaxation of the binary polynomially constrained polynomial programming problem at these Lagrange multipliers, providing the unconstrained binary quadratic programming problem to a binary optimizer, obtaining from the binary optimizer at least one corresponding solution, using the at least one corresponding solution to generate a new set of Lagrange multipliers; and providing all corresponding best-known primal-dual pairs and best-known feasible solutions after convergence.