Note: Descriptions are shown in the official language in which they were submitted.
CA 02921711 2016-02-23
- 1 -
METHOD AND SYSTEM FOR SOLVING THE LAGRANGIAN DUAL
OF A BINARY POLYNOMIALLY CONSTRAINED POLYNOMIAL
PROGRAMMING PROBLEM USING A QUANTUM ANNEALER
FIELD
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 polynomially constrained polynomial programming.
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to Canadian Patent Application No. 2,881,033.
BACKGROUND
Background information on duality and Lagrangian dual of a quadratic binary
programming problem can be found in Canadian Patent application No. 2,881,033.
In duality theory, several different types of dualization and dual problems
are
proposed. One type of dual problems are the Lagrangian dual problems. A
thorough description of Lagrangian duality theory is disclosed in "Nonlinear
integer
programming" by Duan Li and Xiaoling Sun.
For applications of Lagrangian
techniques in discrete optimization, refer to "A survey of Lagrangean
techniques for
discrete optimization" by Jeremy F. Shapiro, Operations Research Center,
Massachusetts Institute of Technology, Cambridge, Massachusetts, and to
"Lagrangean relaxation for integer programming" by A.M. Geoffrion, Mathematics
Programming Study 2 (1974) 82-114, North-Holland Publishing Company.
There are several methods proposed for solving the Lagrangian dual
problems, e.g., subgradient method, outer Lagrangian linearization method, and
bundle method as disclosed in Chapter 3 of "Nonlinear integer programming" by
Duan Li and Xiaoling Sun. The difficulty of having efficient implementations
of such
algorithms is the urge for efficient methods for solving hard nonlinear
integer
programming problems in various stages of these methods. For example, the
single
CA 02921711 2016-02-23
- 2 -
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 of
"Nonlinear integer programming" by Duan Li and Xiaoling Sun, but the proposed
method cannot be generalized for multi-dimensional knapsack problems.
Canadian Patent Application No. 2,881,033 discloses a method for solving
the Lagrangian dual of a constrained quadratic programming problem using a
quantum annealer. The method disclosed is based on an outer Lagrangian
linearization method. Unfortunately, a limitation of this method when used in
conjunction with a quantum annealer is that there may be an appearance of
error-
prone unconstrained quadratic optimization problems in the process.
There is a need for a method for solving a Lagrangian dual optimization
problem that will overcome at least one of the above-identified drawback.
Features of the invention will be apparent from review of the disclosure,
drawings and description of the invention below.
BRIEF SUMMARY
According to a broad aspect, there is disclosed a method for solving the
Lagrangian dual of a binary polynomially constrained polynomial programming
problem, the method comprising 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
quantum annealer, obtaining from the quantum annealer 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
of the Lagrangian dual of the binary polynomially constrained polynomial
programming problem and best-known feasible solutions of the binary
polynomially
constrained polynomial programming problem after the convergence.
CA 02921711 2016-02-23
- 3 -
According to an embodiment, the obtaining of a binary polynomially
constrained polynomial programming problem comprises obtaining data
representative of a polynomial objective function; obtaining data
representative of
polynomial equality constraints; and obtaining data representative of
polynomial
inequality constraints.
According to an embodiment, the binary polynomially constrained polynomial
programming problem is obtained from at least one of a user, a computer, a
software package and an intelligent agent.
According to an embodiment, the obtaining of the binary polynomially
constrained polynomial programming problem further comprises initializing
software
parameters and obtaining a step size subroutine.
According to an embodiment, the initializing of the software parameters
comprises providing a generic degree reduced form of the generic Lagrangian
relaxations of the binary polynomially constrained polynomial programming
problem
as a parameterized family of binary quadratic functions in the original and
auxiliary
variables, parameterized by the Lagrange multipliers. According to an
embodiment,
the initializing of the software parameters also comprises providing a generic
embedding of the generic degree reduced forms of the generic Lagrangian
relaxations of the binary polynomially constrained polynomial programming
problem;
providing an embedding solver function for providing a list of solutions;
providing one
of initial values and default values for Lagrange multipliers and providing an
error
tolerance value for the convergence criteria; providing an integer
representative of a
limit on the total number of iterations; and a limit on the total number of
non-
improving iterations.
According to an embodiment, an initial Lagrangian relaxation of the binary
polynomially constrained polynomial programming problem is generated using the
initial Lagrange multipliers.
According to an embodiment, the initial degree reduced form of the
Lagrangian relaxation of the binary polynomially constrained polynomial
CA 02921711 2016-02-23
,
- 4 -
programming problem is solved using the quantum annealer and at least one
corresponding solution is obtained.
According to an embodiment, the at least one corresponding solution is used
to generate a subgradient of the Lagrangian dual of the binary polynomially
constrained polynomial programming problem.
According to an embodiment, the providing of a corresponding solution to the
Lagrangian dual of the binary polynomially constrained polynomial programming
problem comprises storing the corresponding solution in a file.
According to a broad aspect, there is disclosed 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 a Lagrangian dual of a binary polynomially
constrained
polynomial programming problem, the application comprising instructions for
obtaining a binary polynomially constrained polynomial programming problem;
instructions for iteratively providing a set of Lagrange multipliers, for
providing an
unconstrained binary quadratic programming problem representative of the
Lagrangian relaxation of the binary polynomially constrained polynomial
programming problem at these Lagrange multipliers, for providing the
unconstrained
quadratic programming problem to the quantum annealer using the communication
port, 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 set of Lagrange multipliers until a convergence is detected;
instructions for providing all corresponding best-known primal-dual pairs of
the
Lagrangian dual of the binary polynomially constrained polynomial programming
problem and best-known feasible solutions of the binary polynomially
constrained
polynomial programming problem after the convergence is detected and a data
bus
for interconnecting the central processing unit, the display device, the
communication port and the memory unit.
CA 02921711 2016-02-23
- 5 -
According to a broad aspect, there is disclosed 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 binary polynomially constrained polynomial programming problem, the
method comprising 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 a Lagrangian relaxation of the binary polynomially
constrained polynomial programming problem at these Lagrange multipliers,
providing the unconstrained binary quadratic 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 set of
Lagrange
multipliers; and providing all corresponding best-known primal-dual pairs of
the
Lagrangian dual of the binary polynomially constrained polynomial programming
problem and best-known feasible solutions of the binary polynomially
constrained
polynomial programming problem after the convergence is detected.
An advantage of the method disclosed herein for solving the Lagrangian dual
of a binary polynomially constrained polynomial programming problem is that it
is
less sensitive to errors of the quantum systems. Those errors may be caused by
noisy quantum bits used in some implementations of quantum annealers (e.g. D-
Wave Systems).
Another advantage of the method disclosed herein is that it provides a
method for using Lagrangian duality in various applications, for example
finding
Lagrangian based bounds to integer and mixed-integer programming problems
using a quantum annealer.
Another advantage of the method disclosed herein is that it improves the
processing of a system for solving a Lagrangian dual of a binary polynomially
constrained polynomial programming problem.
CA 02921711 2016-02-23
- 6 -
DESCRIPTION OF THE DRAWINGS
In order that the invention may be readily understood, embodiments of the
invention are illustrated by way of example in the accompanying drawings.
Figure 1 is a flowchart that shows an embodiment of a method for solving a
Lagrangian dual of a binary polynomially constrained polynomial programming
problem using a quantum annealer.
Figure 2 is a diagram of an embodiment of a system in which the method for
solving a Lagrangian dual of a binary polynomially constrained polynomial
programming problem using a quantum annealer may be implemented. In this
embodiment, the system comprises a digital computer and a quantum annealer.
Figure 3 is a diagram that shows an embodiment of a digital computer used in
the system for solving a Lagrangian dual of a binary polynomially constrained
polynomial programming problem using a quantum annealer.
Figure 4 is a flowchart that shows an embodiment for providing a binary
polynomially constrained polynomial programming problem.
Figure 5 is a flowchart that shows an embodiment for initializing software
parameters used in an embodiment of the method for solving a Lagrangian dual
of a
binary polynomially constrained polynomial programming problem.
Figure 6 is a flowchart that shows an embodiment of the proposed method for
updating the Lagrange multipliers.
Further details of the invention and its advantages will be apparent from the
detailed description included below.
DETAILED DESCRIPTION
In the following description of the embodiments, references to the
accompanying drawings are by way of illustration of an example by which the
invention may be practiced.
CA 02921711 2016-02-23
- 7 -
Terms
The term "invention" and the like mean "the one or more inventions disclosed
in this application," unless expressly specified otherwise.
The terms "an aspect," "an embodiment," "embodiment," "embodiments," "the
embodiment," "the embodiments," "one or more embodiments," "some
embodiments," "certain embodiments," "one embodiment," "another embodiment"
and the like mean "one or more (but not all) embodiments of the disclosed
invention(s)," unless expressly specified otherwise.
A reference to "another embodiment" or "another aspect" in describing an
embodiment does not imply that the referenced embodiment is mutually exclusive
with another embodiment (e.g., an embodiment described before the referenced
embodiment), unless expressly specified otherwise.
The terms "including," "comprising" and variations thereof mean "including but
not limited to," unless expressly specified otherwise.
The terms "a," "an", "the" and "at least one", mean "one or more," unless
expressly specified otherwise.
The term "plurality" means "two or more," unless expressly specified
otherwise.
The term "herein" means "in the present application, including anything which
may be incorporated by reference," unless expressly specified otherwise.
The term "e.g." and like terms mean "for example," and thus does not limit the
term or phrase it explains. For example, in a sentence "the computer sends
data
(e.g., instructions, a data structure) over the Internet," the term "e.g."
explains that
"instructions" are an example of "data" that the computer may send over the
Internet,
and also explains that "a data structure" is an example of "data" that the
computer
may send over the Internet. However, both "instructions" and "a data
structure" are
merely examples of "data," and other things besides "instructions" and "a data
structure" can be "data."
CA 02921711 2016-02-23
- 8 -
The term "i.e." and like terms mean "that is," and thus limits the term or
phrase it explains. For example, in the sentence "the computer sends data
(i.e.,
instructions) over the Internet," the term "i.e." explains that "instructions"
are the
"data" that the computer sends over the Internet.
The term "binary polynomially constrained polynomial programming problem"
and like terms mean finding the minimum of a real polynomial y = f(x) in
several
binary variables x = (x1, ...,xn) subject to a (possibly empty) family of
equality
constraints determined by a (possibly empty) family of m equations g1(X) = 0
for
j = 1, ...,m and a (possibly empty) family of inequality constraints
determined by a
(possibly empty) family of (inequalities hi(x) 5_ 0 for] = 1, ..., ( Here all
functions gi
and hj are polynomials.
min f(x)
subject to g(x) = 0 Vi E [1, ...,m)
hi(x) 5_ 0 Vj E [1,
xk E (0,1) Vk E ...,n)
The term "domain" of the binary polynomially constrained polynomial
programming problem, refers to the set fO, 1)n of vectors of size n with
binary
entries.
The term "feasible domain" of the binary polynomially constrained
polynomial programming problem, refers to the subset F t0,1}n of the domain
consisting of all binary vectors v E [0,1}n that satisfy all the m equality
and f
inequality constraints above.
The above binary polynomially constrained polynomial programming problem
will be denoted by (P) and the optimal value of it will be denoted by v(P). An
optimal solution x, i.e., a vector at which the objective function attains the
value v(P)
will be denoted by x*.
The term "Lagrangian function" of the binary polynomially constrained
polynomial programming problem (P), means the following function:
CA 02921711 2016-02-23
- 9 -
m
L (x, kt) = f (x) + IAigi(x) + pihj (x)
The term "Lagrangian relaxation" of the binary polynomially constrained
polynomial programming problem (P), corresponding to fixed Lagrange
multipliers
A E lam and E 111;0, is defined as
op(A, = min f(x) + IAigi(x) + h( x)
xEtomn
j=1
The value of the above optimization, denoted as p(A, 1.1) is known to be a
lower bound for the optimal value of the original binary polynomially
constrained
polynomial programming, that is, ap(A, ) 5_ v(P).
The term "generic Lagrangian relaxation" of the binary polynomially
constrained polynomial programming problem (P), means the parameterized family
{LA,P(x))tAElleneakto) of functions of x where for every choice of parameters
X c 111711
and c ikto we have
(x) = L (x, i7t) .
The term "Lagrangian dual" of a binary polynomially constrained polynomial
programming problem, is used for the following optimization problem:
max min f (x) + IAigi(x) +
(x)
i=1 j=1
subject to x E [0, 1171
A E IRm
E llIto
The value of the above optimization is denoted by ô(P) and is known to be a
lower bound for the optimal value of the original binary polynomially
constrained
polynomial programming, that is, 8(P) v(P) . This value is unique and is also
CA 02921711 2016-02-23
- 1 0 -
called the "Lagrangian dual bound" for the original binary polynomially
constrained
polynomial programming problem.
The term "optimal Lagrange multiplier," and the like, will refer to a, not
necessarily unique, set of points A.* and i at which the value 8(P) is
attained in the
above optimization problem.
The term "solution to the Lagrangian dual problem" of an original binary
polynomially constrained polynomial programming problem, refers to the
following
collection of information received after solving the Lagrangian dual problem:
(1) the
Lagrangian dual bound; (2) a set of (not necessarily unique) optimal Lagrange
multipliers as described above; and (3) a set of (not necessarily unique)
binary
vectors at which the optimal value of the Lagrangian dual problem is obtained
at the
given optimal Lagrange multipliers.
The term "primal-dual pair" refers to a vector (
rt) where )C is
representative of a (not necessarily unique) binary vector at which the
optimal value
of the Lagrangian relaxation corresponding to the Lagrange multipliers (,?,-.1-
) is
obtained.
The term "optimal primal-dual pair" refers to a primal-dual pair (x* , 2* ,
if) for
which 6p (IV, *) attains the optimal value 6(P).
The term "best-known primal-dual pair" refers to a primal-dual pair (x, A, )
for
which Sp(A, it) is the largest observed value of the function 6, during a
running
process.
The term "best-known feasible solution" refers to a feasible vector X* for
which f(V) is the lowest amongst all observed feasible solutions of (P).
The term "quantum annealer" and like terms mean a system consisting of one
or many types of hardware that can find the optimal or sub-optimal solutions
to an
unconstrained binary polynomial programming problem. An example of this is a
system consisting of a digital computer embedding a binary polynomially
constrained
polynomial programming as an !sing spin model, attached to an analog computer
that carries optimization of a configuration of spins in an Ising spin model
using
CA 02921711 2016-02-23
- 11 -
quantum annealing as described, for example, in Farhi, E. et al., "Quantum
Adiabatic
Evolution Algorithms versus Simulated Annealing" arXiv.org:quant ph/0201031
(2002), pp. 1-16. An embodiment of such analog computer is disclosed by
McGeoch, Catherine C. and Cong Wang, (2013), "Experimental Evaluation of an
Adiabiatic Quantum System for Combinatorial Optimization" Computing
Frontiers,"
May 14-16, 2013 (http://www.cs.amherst.edu/ccm/cf14-mcgeoch.pdf) and also
disclosed in the Patent Application US 2006/0225165. It will be appreciated
that the
"quantum annealer" may also be comprised of "classical components," such as a
classical computer. Accordingly, a "quantum annealer" may be entirely analog
or an
analog-classical hybrid.
The term "generic degree reduced form" of the generic Lagrangian relaxation
of the binary polynomially constrained polynomial programming problem (P)
refers
to a parameterized family tqA t
,p(x,y)},AEllm R;oi , of quadratic functions together with
t,tiE
an assignment aux: tyl,
2tx1'...'xn} of a subset of components of x to each
component of y.
The term "embedding" of a binary optimization problem, and the like, refer to
an assignment emb:
, yt) 2tql¨qN} of a subset of all the quantum
bits of the quantum annealer to each binary variable xi and each auxiliary
variable
y such that the connecitivities between the variables are respected by the
connectivities of their images under emb . For examples, the subsets of qubits
corresponding to two variable xr and xs should have a coupling between them in
the
quantum annealer if the term xrx, appears in the generic degree reduced form
of the
generic Lagrangian relaxation of the binary polynomially constrained
polynomial
programming problem. Specifications of the role of such an embedding in
solving an
unconstrained binary polynomial programming problem and presentation of an
efficient algorithm for it are disclosed, for instance, in "A practical
heuristic for finding
graph minors," Jun Cai, William G. Macready, Aidan Roy, in U.S. Patent
Application
US 2008/0218519 and in U.S. Patent US 8,655,828 B2.
CA 02921711 2016-02-23
- 12 -
The term "embedding solver," and the like, refer to a function, procedure, and
algorithm that consist of instructions for receiving an unconstrained binary
quadratic
programming problem, carrying a query to the quantum annealer using a provided
embedding, and returning at least one result, each result containing a vector
of
binary entries, representative of a binary point in the domain of the provided
unconstrained binary quadratic programming, the value of the objective
function of
unconstrained binary quadratic programming at that point, and the number of
occurrences of the result in the entire number of reads.
The term "subroutine" and the like, refer to a user-defined function,
procedure, or algorithm that is called iteratively by the software throughout
the run
time. In the system disclosed herein, the step-size subroutine determines a
next
step-size for the iteration disclosed in Fig. 1. In the system disclosed
herein, the
embedding solver subroutine handles the queries to the quantum annealer
provided
an embedding.
The term "unconstrained binary quadratic programming problem" and like
terms mean finding a minimum of an objective function y = xtQ x + b where Q is
a
symmetric real square matrix of size n, and b is a real number, also known as
the
bias of the objective function. The domain of the function is all vectors x c
Bn =
[0,1)71 with binary entries.
An important class of binary polynomially constrained polynomial
programming problems is that of quadratically constrained ones. The term
"binary
quadratically constrained quadratic programming problem," and the like, refer
to the
class of binary polynomially constrained polynomial programming problems for
which all functions gi and hi are linear or degree two polynomials. Hence the
problem can be rewritten as
CA 02921711 2016-02-23
- 13 -
min f (x)
subject to Aegx = beg
Aineci X bine('
xt Aiegx = bq Vi E {1,
xt 4egx 5_ bineg Vi E {1, ..., q}
xi E 0,1} Vi E f1,
where y = f (x) is a quadratic polynomial of several binary variables x =
(x1,...,x)
subject to a (possibly empty) family of linear equality constraints determined
by a
linear system Aegx = beg where Aeg is a matrix of size m x n and beg is a
column
matrix of size m x 1 and a (possibly empty) family of inequality constraints
determined by AineqX bineg where Aineg is a matrix of size (x n and bineq is a
column matrix of size (x 1. Also subject to a (possibly empty) family of
quadratic
equality constraints determined by a set of p equations xt Aiegx = bieg where
Aleg is of
size n x n and kg is a real number for each i E [1, ===, p} . Also subject to
a (possibly
empty) family of quadratic inequality constraints determined by a set of q
inequalities
xtAnegx btneg where ALeg is of size n x n and bineg is a real number for each
E f1,===, q}
Neither the Title nor the Abstract is to be taken as limiting in any way as
the
scope of the disclosed invention(s). The title of the present application and
headings
of sections provided in the present application are for convenience only, and
are not
to be taken as limiting the disclosure in any way.
Numerous embodiments are described in the present application, and are
presented for illustrative purposes only. The described embodiments are not,
and
are not intended to be, limiting in any sense. The presently disclosed
invention(s)
are widely applicable to numerous embodiments, as is readily apparent from the
disclosure. One of ordinary skill in the art will recognize that the
disclosed
invention(s) may be practiced with various modifications and alterations, such
as
structural and logical modifications. Although particular features of the
disclosed
invention(s) may be described with reference to one or more particular
embodiments
CA 02921711 2016-02-23
- 14 -
and/or drawings, it should be understood that such features are not limited to
usage
in the one or more particular embodiments or drawings with reference to which
they
are described, unless expressly specified otherwise.
It will be appreciated that the invention may be implemented in numerous
ways, including a method, a system, a computer readable medium such as a
computer readable storage medium. In this specification, these
implementations, or
any other form that the invention may take, may be referred to as systems or
techniques. A component such as a processor or a memory described as being
configured to perform a task includes both a general component that is
temporarily
configured to perform the task at a given time or a specific component that is
manufactured to perform the task.
With all this in mind, the present invention is directed to a method and
system
for solving a Lagrangian dual of a binary polynomially constrained polynomial
programming problem.
Now referring to Fig. 2, there is shown an embodiment of a system 200 in
which an embodiment of the method for solving a Lagrangian dual of a binary
polynomially constrained polynomial programming problem may be implemented.
The system 200 comprises a digital computer 202 and a quantum
annealer 204.
The digital computer 202 receives a binary polynomially constrained
polynomial programming problem and provides at least one solution to the
Lagrangian dual of the binary polynomially constrained polynomial programming
problem.
It will be appreciated that the binary polynomially constrained polynomial
programming problem may be provided according to various embodiments.
In one embodiment, the binary polynomially constrained polynomial
programming problem is provided by a user interacting with the digital
computer 202.
CA 02921711 2016-02-23
- 15 -
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by another computer, not shown, operatively connected to
the
digital computer 202.
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by an independent software package.
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by an intelligent agent.
Similarly, it will be appreciated that the at least one solution to the
Lagrangian
dual of the binary polynomially constrained polynomial programming problem may
be provided according to various embodiments.
In accordance with an embodiment, the at least one solution to the
Lagrangian dual of the binary polynomially constrained polynomial programming
problem is provided to the user interacting with the digital computer 202.
Alternatively, the at least one solution to the Lagrangian dual of the binary
polynomially constrained polynomial programming problem is provided to another
computer operatively connected to the digital computer 202.
In fact, it will be appreciated by the skilled addressee that the digital
computer
202 may be any type of computer.
In one embodiment, the digital computer 202 is selected from a group
consisting of desktop computers, laptop computers, tablet PCs, servers,
smartphones, etc.
Now referring to Fig. 3, there is shown an embodiment of a digital computer
202. It will be appreciated that the digital computer 202 may also be broadly
referred to as a processor.
In this embodiment, the digital computer 202 comprises a central processing
unit (CPU) 302, also referred to as a microprocessor, a display device 304,
input
devices 306, communication ports 308, a data bus 310 and a memory unit 312.
CA 02921711 2016-02-23
- 16 -
The CPU 302 is used for processing computer instructions. The skilled
addressee will appreciate that various embodiments of the CPU 302 may be
provided.
In one embodiment, the central processing unit 302 is a CPU Core i7-3820
running at 3.6 GHz and manufactured by Interm).
The display device 304 is used for displaying data to a user. The skilled
addressee will appreciate that various types of display device 304 may be
used.
In one embodiment, the display device 304 is a standard liquid-crystal display
(LCD) monitor.
The communication ports 308 are used for sharing data with the digital
computer 202.
The communication ports 308 may comprise, for instance, a universal serial
bus (USB) port for connecting a keyboard and a mouse to the digital computer
202.
The communication ports 308 may further comprise a data network
communication port such as an IEEE 802.3 port for enabling a connection of the
digital computer 202 with another computer via a data network.
The skilled addressee will appreciate that various alternative embodiments of
the communication ports 308 may be provided.
In one embodiment, the communication ports 308 comprise an Ethernet port
and a mouse port (e.g., Logitech(Tm)).
The memory unit 312 is used for storing computer-executable instructions.
It will be appreciated that the memory unit 312 comprises, in one
embodiment, an operating system module 314.
It will be appreciated by the skilled addressee that the operating system
module 314 may be of various types.
In an embodiment, the operating system module 314 is Windows(TM) 8
manufactured by Microsoft(Tm).
CA 02921711 2016-02-23
.*..
- 17 -
The memory unit 312 further comprises an application for solving the
Lagrangian dual of a binary polynomially constrained polynomial programming
problem 316.
The application 316 comprises instructions for obtaining a binary polynomially
constrained polynomial programming problem.
The application 316 further comprises instructions for 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
quantum annealer; obtaining from the quantum annealer at least one
corresponding
solution and for using the at least one corresponding solution to generate a
new set
of Lagrange multipliers.
The application 316 further comprises instructions for providing a
corresponding at least one solution to the Lagrangian dual of the binary
polynomially
constrained polynomial programming problem once a convergence is detected.
Each of the central processing unit 302, the display device 304, the input
devices 306, the communication ports 308 and the memory unit 312 is
interconnected via the data bus 310.
Now referring back to Fig. 2, it will be appreciated that the quantum annealer
204 is operatively connected to the digital computer 202.
It will be appreciated that the coupling of the quantum annealer 204 to the
digital computer 202 may be achieved according to various embodiments.
In one embodiment, the coupling of the quantum annealer 204 to the digital
computer 202 is achieved via a data network.
It will be appreciated that the quantum annealer 204 may be of various types.
In one embodiment, the quantum annealer 204 is manufactured by D-Wave
Systems Inc. More information on this embodiment of a quantum annealer
applicable to 204 may be found at http://www.dwavesys.com. The skilled
addressee
CA 02921711 2016-02-23
- 18 -
will appreciate that various alternative embodiments may be provided for the
quantum annealer 204.
More precisely, the quantum annealer 204 receives an unconstrained binary
quadratic programming problem from the digital computer 202.
The quantum annealer 204 is capable of solving the unconstrained binary
quadratic programming problem and of providing at least one corresponding
solution. In the case where a plurality of corresponding solutions is
provided, the
plurality of corresponding solutions may comprise optimal and suboptimal
solutions.
The at least one corresponding solution is provided by the quantum annealer
204 to the digital computer 202.
Now referring to Fig. 1 and according to processing step 102, a binary
polynomially constrained polynomial programming problem is obtained.
Now referring to Fig. 4, there is shown an embodiment for providing a binary
polynomially constrained polynomial programming problem.
As mentioned above, the binary polynomially constrained polynomial
programming problem can be represented as:
min f (x)
subject to g1(x) = 0 Vi E [1,
h1(x) 0 Vj E f1,
xk E t0,1) Vk E (1, , n)
in which the functions f (x), g(X) and hi(x) are real polynomials in several
variables.
According to processing step 402, data representative of a polynomial
objective function f (x) are provided.
According to processing step 404, data representative of the equality and
inequality constraints g i(x) and h1(x) are provided.
It will be appreciated that the obtaining of a binary polynomially constrained
polynomial programming problem may be performed according to various
embodiments.
CA 02921711 2016-02-23
- 19 -
As mentioned above and in one embodiment, the binary polynomially
constrained polynomial programming problem is provided by a user interacting
with
the digital computer 202.
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by another computer operatively connected to the digital
computer 202.
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by an independent software package.
Alternatively, the binary polynomially constrained polynomial programming
problem is provided by an intelligent agent.
Now referring to Fig. 1 and according to processing step 104, parameters of
the software are initialized.
In one embodiment, the parameters of the software are initialized by the
digital computer 202.
Now referring to Fig. 5, there is shown an embodiment for initializing
parameters and subroutines or using default values for them.
According to processing step 502, a generic degree reduced form of the
generic Lagrangian relaxations of the binary polynomially constrained
polynomial
programming problem is provided.
According to processing step 504, data representative of a generic
embedding of the generic degree reduced form of the generic Lagrangian
relaxations of the binary polynomially constrained polynomial programming
problem
is provided.
In one embodiment, the embedding is stored by a user in the namespace
ORACLE, as ORACLE: : embedding.
Still referring to Fig. 5 and according to processing step 506, an embedding
solver subroutine is provided.
In one embodiment, the function is implemented by the user in the
namespace ORACLE, as ORACLE: : solve qubo.
CA 02921711 2016-02-23
- 20 -
The input parameter of the embedding solver subroutine is a pointer to an
instance of the data type ORACLE: :qubo, representative of an unconstrained
binary
quadratic programming neglecting the corresponding bias of it.
The output of the embedding solver subroutine is a pointer to an instance of
the type ORACLE: :result, representative of a list of optimal and suboptimal
solutions to the unconstrained binary polynomial programming problem.
The following is an example of a code snippet in C++ for providing the
subroutine using the API developed by D-Wave Systems (Sapi 2.0). All the
functions
and types used in this snippet are supported by Sapi 2.0 except two auxiliary
functions qubo_to_ising and spin to binary. The former function changes
an unconstrained binary quadratic programming problem of type ORACLE: :qubo,
to
an lsing spin problem of type sapi_problem by a change of variables s = 2x ¨
1.
The second function received an array of vectors in f-1,1} and returns binary
vectors by applying the inverse transformation x = ¨21 S 1).
#include <stdio.h>
#include <stdlib.h>
#include "dwave_sapi.h"
ORACLE::result* main(ORACLE::qubo& qubo) {
sapi_globalInit();
sapi_Problem* A = NULL;
sapi_Problem* emb = NULL;
sapi_Problem problem = qubo_to ising(qubo);
sapi_Embeddings* embeddings fiULL;
sapi_FindEmbeddingParameters finder_param =
SAPI_FIND_EMBEDDING_DEFAULT_PARAMETERS;
sapi_IsingRangeProperties* range prop = NULL;
sapi_EmbedProblemResult* res . NULL;
sapi_QuantumSolverParameters params =SAPI_QUANTUM_SOLVER_DEFAULT_PARAMETERS;
sapi_IsingResult* answer = NULL;
int* new solutions = NULL;
double ci;ain_strength= -2.0;
char err_msg[SAPI_ERROR_MESSAGE_MAX_SIZE];
const char* un =
const char* token = ".
sapi_Connection* connection = NULL;
sapi_remoteConnection(url, token, NULL, &connection, err_msg);
CA 02921711 2016-02-23
-21 -
sapi_getHardwareAdjacency(solver, &A);
sapi_findEmbedding(&problem, A, &finder_param, &embeddings, err_msg);
sapi_embedProblem(&problem, embeddings, A,0,0, range prop, &res, err_msg);
/* allocate space for new embedded problem result */
emb = malloc(sizeof(sapi Problem*));
emb->len = res->problem.ien + res->jc.len;
emb->elements = (sapi_ProblemEntry*)malloc(sizeof(sapi_ProblemEntry) * emb-
>len);
/* store embedded problem result in new problem */
for(index = 0; index < res->problem.len; index++) {
emb->elements[index].i = res->problem.elements[index].i;
emb->elements[index].j = res->problem.elements[index].j;
emb->elements[index].value = res->problem.elements[index].value;
for(; index < emb->len; index++) {
emb->elements[index].i = res->jc.elements[index - res->problem.len].i;
emb->elements[index].j = res->jc.elements[index - res->problem.len].j;
emb-elements[index].value = chain_strength;
params.num reads = 1000;
sapi_solveising(solver, emb, (sapi_SolverParameters*)¶ms,
&answer,err_msg);
size_t num_new_solutions;
new_solutions = malloc(answer->num_solutions * num variables * sizeof(int*));
sapi_unembedAnswer(answer->solutions, answer->soluiion_len, answer-
>num_solutions,
embeddings, SAPI BROKEN CHAINS_MINIMIZE ENERGY, &problem, new_solutions,
&num_new_solutions, err_msg);
return spin_to_binary(new_solutions);
It will be appreciated that, in one embodiment, the providing of the
unconstrained binary optimization problem to the quantum annealer 204 is
achieved
using the digital computer 202.
More precisely, it will be appreciated that in one embodiment a token system
is used over the Internet to provide access to the quantum annealer 204
remotely
and to authenticate use.
It will be appreciated that in one embodiment the at least one solution is
provided in a table by the quantum annealer 204, according to the instructions
of use
of the quantum annealer 204.
In one embodiment, the D-Wave system, provides the at least one solution in
the data type sapi_IsingResult* which is then type-casted automatically to an
instance of QUBO: :result*.
CA 02921711 2016-02-23
- 22 -
Still referring to Fig. 5 and according to processing step 508, lower and
upper
bounds for Lagrange multipliers are provided.
It will be appreciated that in one embodiment the providing of these real
numbers of type double is achieved by overwriting the names ORACLE: :dual_lb
and ORACLE: :dual ub. Each of these types will be required to contain an array
of
doubles of size m + f. The first m entries of these arrays represent,
respectively, the
lower and upper bounds for the Lagrange multipliers corresponding to the m
equality
constraints and the last (of them represent, respectively, the lower and upper
bounds for the Lagrange multipliers corresponding to the f inequality
constraints.
It will be appreciated that if these names are not overwritten, the values of
them are initialized with the default values.
In one embodiment, the default lower bound for a Lagrange multiplier
corresponding to an equality constraint is -1e3 and the default upper bound
for it
is +1e3.
The default lower bound for a Lagrange multiplier corresponding to an
inequality constraint is 0 and the default upper bound for it is +1e3.
Still referring to Fig. 5 and according to processing step 510, initial values
for
the Lagrange multipliers are provided.
It will be appreciated that the providing of these real valued numbers is
achieved by overwriting the name ORACLE: :dual_init_val with an array of
doubles of size m +
If this name is not overwritten, the values are initialized with
default values.
The default initial value for any of the Lagrange multipliers, corresponding
to
any of equality or inequality constraints, is 0.
According to processing step 512, an error tolerance value on the norm of a
subgradient of the Lagrangian dual is provided. If the norm of any subgradient
of the
Lagrangian relaxation falls below this tolerance, it is assumed that strong
duality
holds. In such case, the Lagrange multipliers are optimal. Unless overwritten
by the
user and according to one embodiment, the error tolerance value is initialized
to
CA 02921711 2016-02-23
- 23 -
le-5 and stored as ORACLE: :tol. The error tolerance value is used in several
points in the software.
According to one embodiment, ORACLE: :tol is used for checking equality
and inequality conditions. In particular, any system of inequalities LHS < RHS
is
considered satisfied if the value of all entries in LHS ¨ RHS is at most
ORACLE: :tol. Similarly, any system of equalities LHS = RHS is considered
satisfied if the absolute value of all entries in LHS ¨ RHS is at most ORACLE:
:tol.
Still referring to Fig. 5 and according to processing step 514, a limit on the
total number of iterations is provided.
Unless overwritten by the user and according to one embodiment, the limit on
the number of iterations is initialized to 1e3 and stored as ORACLE: :MaxItr .
If the algorithm reaches ORACLE: :MaxItr iterations of the processing step
116, it terminates and returns the at least one best-known primal-dual pair
and the at
least one best-known feasible solution.
According to processing step 514, a limit on the number of non-improving
iterations is provided.
Unless overwritten by the user and according to one embodiment, the limit on
the number of iterations is initialized to 10 and stored as
ORACLE::MaxNonImpItr.
If the best-known Lagrangian dual value does not
increase in ORACLE: :MaxNonImpItr iterations, the algorithm terminates and
returns the at least one best-known primal-dual pair and the at least one best-
known
feasible solution.
According to processing step 516, a subroutine for finding the step size is
provided.
In one embodiment, the subroutine is implemented by the user in the
namespace ORACLE, as ORACLE::StepSize. If ORACLE::StepSize is not
overwritten by the user, a fixed step size for a default value is used.
CA 02921711 2016-02-23
- 24 -
In one embodiment, the subroutine ORACLE: :StepSize receives as input,
an object of type double* representative of a search direction and returns as
output, an object of type double representative of a step size.
In one embodiment, the search direction is the subgradient of the Lagrangian
dual function and the step size is the fixed value of 1.
Now referring back to Fig. 1 and according to processing step 106, an
unconstrained binary quadratic programming problem representative of the
Lagrangian relaxation of the binary polynomially constrained polynomial
programming problem (P) at the current values of the Lagrange multipliers is
generated.
It will be appreciated that in one embodiment, the unconstrained binary
quadratic programming problem representative of the Lagrangian relaxation of
the
binary polynomially constrained polynomial programming problem (P) at the
current
values of the Lagrange multipliers is generated by the digital computer 202.
More precisely, it will be appreciated that in the present embodiment, the
generation of the unconstrained binary quadratic programming problem is
achieved
by substituting the current values of the Lagrange multipliers for the
parameters A
and in the generic degree reduced form q(x,y) of the generic Lagrangian
relaxations of the binary polynomially constrained polynomial programming
problem (P).
In one embodiment, the information of the unconstrained binary quadratic
programming problem is stored in the name ORACLE: :qubo.
Still referring to Fig. 1 and according to processing step 108, the subroutine
ORACLE: : solve qubo is called with the unconstrained binary quadratic
programming problem ORACLE: :qubo and the embedding ORACLE: :embedding
as inputs in order to provide at least one corresponding solution for the
unconstrained binary quadratic programming problem from the quantum
annealer 204.
CA 02921711 2016-02-23
-25 -
It will be appreciated that the at least one corresponding solution of the
unconstrained binary quadratic programming problem is achieved in one
embodiment with a pointer to an instance of type ORACLE: : result.
Still referring to Fig. 1 and according to processing step 110, the at least
one
solution to the unconstrained binary quadratic programming problem is
converted to
a point in the domain of the binary polynomially constrained polynomial
programming problem (P).
Still referring to Fig. 1 and according to processing step 112, a test is
performed in order to determine if any of the at least one solution for the
unconstrained binary quadratic programming problem corresponds to a feasible
solution to the binary polynomially constrained polynomial programming
problem (P).
According to the same processing step, the at least one best-known primal-
dual pair, and the at least one best-known feasible solution, are updated.
Now referring to processing step 114, at least one corresponding solution of
the unconstrained binary quadratic programming is used to generate a
subgradient
of the Lagrangian relaxation, 8(A, it).
Now referring to Fig. 6, and according to processing step 602, at least one
corresponding binary vector in the domain of the binary polynomially
constrained
polynomial programming problem (P) is provided.
According to processing step 604, a subgradient of the Lagrangian relaxation
corresponding to the solution fe of the unconstrained binary quadratic
programming
problem is derived as:
= giM for i = 1,...,m
CipiL(A, pt) = h1(.5e) for] = 1, ...,-e =
In one embodiment, one may choose the subgradient with the smallest norm
when multiple binary solutions of the unconstrained quadratic programming
problem
is provided.
In one embodiment, one may normalize the derived subgradient.
CA 02921711 2016-02-23
- 26 -
According to processing step 606, the derived subgradient is provided to the
step size subroutine and a value for the step size is attained.
According to an embodiment, if a step size subroutine is initialized by the
user, the step size a is found by a call to ORACLE: : StepSize.
According to processing step 608, the Lagrange multipliers are updated as
follows:
= Art + a VA,/, (), = Art + a gi() for i =
Kew = ityid ti) ityld + &Lim for] = 1,...,e.
Now referring back to Fig. 1 and according to processing step 116, a test is
performed in order to find out if the best-known value of op(il, ) has
improved in the
previous ORACLE: :MaxNonImpItr steps.
In the case where the optimal value of p (A, 11) has not improved in the past
ORACLE: :MaxNonImpItr steps and according to processing step 118, the results
of the optimization are provided.
It will be appreciated that in one embodiment, the results comprise the set of
all best known primal-dual pairs (x* , A* , if) and all best known feasible
solutions.
In one embodiment, the results are stored using the digital computer in a
file.
It will be appreciated that an advantage of the method disclosed herein is
that
it enables an efficient method for finding the solution of a binary
polynomially
constrained polynomial programming problem by finding the solution of its
Lagrangian dual using a quantum annealer.
It will be further appreciated that the method disclosed herein improves the
processing of a system for solving a Lagrangian dual of a binary polynomially
constrained polynomial programming problem.
It will be appreciated that the Lagrange multipliers are updated iteratively
until
termination. The program terminates when either the norm of the subgradient of
the
Lagrangian dual function is at most ORACLE: :tol or no improvement in the best
CA 02921711 2016-02-23
- 27 -
known primal-dual pair is observed after ORACLE: :MaxNonImpItr iterations, or
after ORACLE: :MaxItr iterations.
The following is an illustration of a use of the method described herein once
applied to the maximum quadratic stable set problem.
Let G = (V, E) define a graph on n vertices; W be a symmetric square matrix
of size n representing the weights of edges E; and A be the adjacency matrix
of G.
The maximum quadratic stable set problem is formulated as
max xtW x,
subject to xt Ax = 0,
xi E tO, 1) Vi E [1, ,
It will be appreciated that by taking the negative of the objective function,
the
maximization objective function may be written as a minimization one as
follows:
min ¨xtW x,
subject to xt Ax = 0,
xi E 0,1} Vi E (1, ..., nj.
Moreover, it will be appreciated that the constraint xt Ax = 0 may be
substituted with xt Ax < 0. This is because both A and x are binary (i.e. xtAx
> 0 for
any
binary vector x c [0, 1.171) SO xt Ax < 0 is satisfied for all binary vectors
x for
which the identity xt Ax = 0 holds. The maximum quadratic stable set problem
can
be solved through the following formulation:
min ¨xt14/ x,
subject to xt Ax < 0,
xi E 0,1} Vi E [1, ...,n).
In one example, let a graph with 5 vertices represent a group of 5 coworkers.
To each pair of coworkers, a utility factor is assigned for the collaboration
between
them. A utility factor is assigned to each individual for their performance;
these
values are on the diagonal of matrix W. The utilities can be represented with
an
upper triangular matrix:
CA 02921711 2016-02-23
- 28 -
/5 0 3 5 2\
0 ¨1 1 ¨1 4
Wit = 0 0 1 7 3 .
I 0 0 0 3 0
\ 0 0 0 0 2/
The utility matrix W may as well be represented by the 5 x 5 symmetric matrix
W = (Wu + Wt). For the above example, W would be:
2
5 0 1.5 2.5 1 \
0 ¨1 0.5 ¨0.5 2 I
W = 1.5 0.5 1 3.5 1.5 .
I 2.5 ¨0.5 3.5 3 0
\ 1 2 1.5 0 2)
Suppose each worker has a working shift and matrix A has nonzero entries
for the pair of coworkers that have overlapping shifts:
/0 0 1 0 1 \
0 0 0 1 0
A= 1 0 0 0 1 .
0 1 0 0 0
\1 0 1 0 0/
The problem of selecting the most productive team for a project such that no
two team-members have overlapped shifts is an instance of the maximum
quadratic
stable set problem.
Give the above-defined matrices A and W the binary polynomially constrained
polynomial programming problem
min ¨xtW x,
subject to xt Ax < 0,
xi E [0, 1) Vi E [1,
is obtained according to processing step 102.
Since the two polynomials in the objective function and the inequality
constraint of the above example are quadratic, the degree reduced form of the
Lagrangian relaxation of this problem is the same as the Lagrangian relaxation
itself.
CA 02921711 2016-02-23
- 29 -
The embedding of a complete graph of size 5 is provided. The following code
snippet provides an embedding of a complete graph of size 5 on a K4,4-
bipartite
chimera block consisting of two parts each of size 4 and indexed by integers 0
to 3
in one part and by integers 4 to 7 in the second part.
sapi Embeddings* ORACLE: :embedding = NULL;
ORACEE::embedding = (sapi_Embeddings*)malloc(sizeof(sapi_Embeddings));
ORACLE::embedding->len = solver_properties->quantum solver->num_qubits;
ORACLE::embedding->elements= malloc(sizeof(int) * eMbeddings->len);
for (int i= 0; i < ORACLE::embedding->len; i++) ORACLE::embedding-
>elements[i]= -1;
ORACLE::embedding->elements[0]= 0;
ORACLE::embedding->elements[1]= 1;
ORACLE::embedding->elements[5]= 1;
ORACLE::embedding->elements[2]= 2;
ORACLE::embedding->elements[6]= 2;
ORACLE::embedding->elements[3]= 3;
ORACLE::embedding->elements[7]= 3;
ORACLE::embedding->elements[4]= 4;
Lower and upper bounds of the Lagrangian multiplier are set as 0 and 100,
respectively. 0 is assigned as the initial value of the Lagrangian multiplier.
The
tolerance on the norm of the subgradient of the Lagrangian dual function is
set to
10-3. The limit on the total number of iterations and the number of non-
improving
iterations is set to 100 and 5, respectively. The step-size subroutine used in
this
example is a subroutine that provides the fixed step size of size 0.5
according to the
following script
double ORACLE::StepSize() { return 0.5; )
When the method starts, the list of best feasible solution and the best primal-
dual pair is initialized as empty sets. The single Lagrangian multiplier of
the
presented method is initialized at 21 = 0, and the problem
min ¨xtVli x
xeto,ip
is solved by a quantum annealer. The attained optimal solution is xl =
(1,1,1,1,1)
and the optimal value is -33. Since xl is not feasible, the list of best
feasible solution
is not updated. The best primal-dual pair, however, is updated as (xl , Al) .
CA 02921711 2016-02-23
- 30 -
The subgradient of the Lagrangian relaxation
min ¨xtW x + A(xtAx)
xEto,tin
is xt Ax = 8 for xl = (1,1,1,1,1). Suppose for the step-size subroutine, a
fixed step-
size of 0.5 is used. The next Lagrangian multiplier is then computed as
.12 = 0 + 0.5 * 8 = 4.
The Lagrangian relaxation problem
min ¨xtW x + 4(xt Ax)
xeto,iin
is solved by a quantum annealer. The optimal solution x2 = (1,0,1,1,0) with
optimal
value -16 is obtained. The best primal-dual pair is updated as (x2,).2), but
the best
feasible solution is left as empty set since x2 is not feasible.
The subgradient of the Lagrangian relaxation at this solution is 2. The next
Lagrangian multiplier is then computed as
2.3 = 4+ 0.5 * 2 = 5.
The Lagrangian relaxation problem
min ¨xtW x + 5(xt Ax)
xEf0,1}n
is solved by a quantum annealer. The optimal solution x3 = (1,0,1,1,0) with
optimal
value -14 is obtained. The best primal-dual pair is updated as (x3,23), but
the best
feasible solution is left as empty set since x3 is not feasible.
The subgradient of the Lagrangian relaxation at this solution is 2. The next
Lagrangian multiplier is then computed as
2.4 = 5 + 0.5 * 2 = 6.
The Lagrangian relaxation problem
min ¨xtW x + 6(xt Ax)
xE{0,1}n
CA 02921711 2016-02-23
- 31 -
is solved by a quantum annealer. The optimal solution x4 = (1,0,0,1,0) with
optimal
value -13 is obtained. x4 is feasible, so the best feasible solution is
updated as well
as the best primal-dual pair (x4, A4).
At the current solution the norm of the subgradient of the Lagrangian
relaxation is 0 and the method terminates. The best feasible solution x4 =
(1,0,0,1,0), and the best primal-dual pair (x4,2.4) = ( (1,0,0,1,0), 6) is
reported.
For the present application, the obtained solution means that among all teams
such that no two coworkers have overlapping shifts, team of workers 1 and 4 is
the
most productive team.
It will be appreciated that an advantage of the method disclosed herein is
that
it improves the processing of a system for solving a Lagrangian dual of a
binary
polynomially constrained polynomial programming problem. More precisely, the
method disclosed herein is less prone to errors than prior-art methods, which
is of
great advantage.
It will be appreciated that a non-transitory computer-readable storage medium
is further disclosed. The non-transitory computer-readable storage medium is
used
for storing computer-executable instructions which, when executed, cause a
digital
computer to perform a method for solving a Lagrangian dual of a binary
polynomially
constrained polynomial programming problem, the method comprising 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
a Lagrangian relaxation of the binary polynomially constrained polynomial
programming problem at these Lagrange multipliers, providing the unconstrained
binary quadratic 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 set of Lagrange multipliers; and
providing
all corresponding best-known primal-dual pairs of the Lagrangian dual of the
binary
polynomially constrained polynomial programming problem and best-known
feasible
CA 02921711 2016-02-23
- 32 -
solutions of the binary polynomially constrained polynomial programming
problem
after the convergence is detected.
Although the above description relates to specific embodiments as presently
contemplated by the inventors, it will be understood that the invention in its
broad
aspect includes functional equivalents of the elements described herein.
