Method and system for solving Lagrange duals of binary polynomially constrained multinomial programming problems using a binary optimizer

摘要

Disclosed are methods and systems for solving Lagrange duals of binary polynomial constrained problems (BPCPPP). The method comprises the steps of obtaining BPCPPP; providing a set of Lagrange multipliers iteratively until convergence is detected, and an unconstrained binary quadratic programming problem representing the Lagrange relaxation of BPCPPP in these Lagrange multipliers ( Provide UBQPP, unconstrained binary quadratic programming problem), provide UBQPP to the binary optimizer, get at least one corresponding solution from the binary optimizer, and set a new Lagrange multiplier using at least one corresponding solution And after convergence, providing all corresponding known best principal duals and known best feasible solutions. [Selected figure] Figure 1