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.

Description

CROSS-REFERENCE TO RELATED APPLICATION[0001]The present patent application claims priority on Canadian Patent Application No. 2,881,033, filed on Feb. 3, 2015.FIELD[0002]The invention relates to computing. More precisely, this invention pertains to a method and system for solving the Lagrangian dual problem corresponding to a binary quadratic programming problem.BACKGROUND[0003]Duality is an important phenomenon in optimization theory. In general, duality is a process of generating a “dual” problem for the original “primal” problem. Solving dual problems provide information about the primal problem.[0004]In some optimization models, duality directly yields alternative viewpoints to the problems. For example, in models of electrical networks, the “primal variables” may represent current flows, whereas the “dual variables” may represent voltage differences. In models of economic markets, “primal variables” may represent production and consumption levels and the “dual variables” may re...

AI Technical Summary

Benefits of technology

The patent describes a method that makes it easier to solve a specific type of mathematical problem. This method can be used to process a system for solving a Larganian dual of a constrained binary quadratic programming problem. Its technical effect is to speed up the processing of this problem.

Problems solved by technology

In a wider range of scenarios, dual problems may yield more complicated information about the optimization model.

These combinatorial optimization problems are models of many problems of interest in operational research; e.g. scheduling problems, job-shop problems, and resource allocation problems.

The difficulty of having efficient implementations of such algorithms is the urge to very efficient methods for solving hard nonlinear integer programming problems in various stages of these methods.

For example, the single constrained quadratic 0-1 knapsack problem can be solved using an efficient branch and bound method based on Lagrangian duality as explained in Section 11.5, “Nonlinear integer programming” by Duan Li and Xiaoling Sun but the proposed method cannot be generalized for multi-dimensional knapsack problems.

Images