Constraint¶
This section explains the classes that represent constraints.
Constraint Condition Object¶
When solving problems with quantum annealing machines and Ising machines, it may be necessary to impose constraint conditions on the used variables.
For example, when searching for the optimal solution of the objective function \(f\left(x_0, x_1, x_2 \right)\) in terms of variables \(x_0, x_1, x_2\) under some constraints, such as an equality constraint like \(x_0 + x_1 + x_2 = 1\) or an inequality constraint like \(x_0 + x_1 + x_2 \leq 2\), we need to find the optimal solution from “feasible solutions” that satisfy the constraints.
However, QUBO and Ising models, with which we need to use for quantum annealing machines and Ising machines, cannot directly handle such constraints. One basic approach to deal with constraint conditions is to prepare a penalty function \(g\), which takes the minimum value if the constraint is satisfied, and add it to the original objective function \(f\) with a weight \(\lambda\).
In other words, instead of \(f\), we can find the optimal solution of \(h = f + \lambda g \quad (\lambda > 0)\) to get a feasible solution whose penalty function \(g\) is minimal, i.e., satisfies the constraints. In practice, the output of the machine is not always the optimal solution, so the feasibility of the solution of \(h\) is identified by checking if \(g\) takes the minimum value.
The Amplify SDK prepares constraint objects, which construct and manage abstract forms of constraint problems, such as formulation of penalty functions, weights of penalty functions, and satisfaction checks when evaluating solutions.
The constraint class represent the constraints imposed on the variables, which are associated with polynomial and matrix classes.
The correspondence between the constraint classes and the polynomial and matrix classes is summarized in the following table:
Polynomial class 
Matrix class 
Constraint class 

A constraint object can be converted into a logical model by giving it to BinaryQuadraticModel
etc. It can be also combined with a polynomial class or matrix class, so that it is treated as an additional constraint condition for a given polynomial or matrix object.
Construction Using a Penalty Function¶
The constraint imposed on the variables \(\mathbf q\) can be expressed by setting a penalty function \(g(\mathbf{q})\) appropriately. \(g (\mathbf{q})\) is a function that takes the minimum value when \(\mathbf{q}\) satisfies the constraint condition. \(g(\mathbf{q})\) is called a penalty function because \(\mathbf{q}\) not satisfying the constraints is penalized in such a way that \(g\) takes a larger value than its minimum.
If the penalty function is known in advance, the following generating function can be used to construct the constraint class.
Constraint 
Generating function 
Condition for use 

\(f\left( \mathbf{q} \right) = 0\) 
\(\min f\left( \mathbf{q} \right) = 0\) 
penalty()
is a basic constraint object that represents a penalty function. It gives a penalty function represented by such a polynomial \(f\) that take the value \(f=0\) if the constraint is satisfied, where its minimum value is \(\min f = 0\).
Constraint by Logical Expression¶
For example, consider a constraint condition that two variables \(q_0\) and \(q_1\) cannot be both \(1\) at the same time. This condition is equivalent to the NAND operation on these variables, for being False
only when both are \(1\) and True
for all the other cases.
For this example, we will first create a constraint object using a logical expression class. See Logical Expression for more details.
A logical expression that represents NOT AND
is constructed as follows:
from amplify import LogicPoly
x = gen_symbols(LogicPoly, 2)
p = ~(x[0] & x[1])
>>> p
 x_0 x_1 + 1
We can see \(p=0\) (False
) when \(x_0=x_1=1\) and \(p=1\) (True
) for all the other cases, as is expected for the result of NOT AND
operation on the two variables \(x_0\) and \(x_1\). To obtain the penalty function \(g(q_0,q_1)\) expressing NOT AND
constraint, we now convert the formula expression p
to a polynomial of binary variables \(q_0\) and \(q_1\). Such a penalty function should take the minimum value of \(0\) only when both of these variables are not \(1\) at the same time. Observing that inverting \(p\) can lead to such a relation, we can perform an operation NOT
on \(p\) in the following way to obtain the penalty function \(g\).
from amplify.constraint import penalty
f = (~p).to_Poly()
g = penalty(f)
>>> g
q_0 q_1 == 0
Now we have the minimization problem, where the penalty function \(g\) takes the minimum value \(0\) for NOT AND
between \(q_0\) and \(q_1\) for True
and a larger value of \(1\) for False
. This demonstrates that the penalty()
function can create a constraint object that expresses the constraint condition which has the optimal and minimum value of \(0\).
from amplify import (
BinaryQuadraticModel,
decode_solution,
gen_symbols,
LogicPoly,
Solver,
)
from amplify.client import FixstarsClient
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True
client.parameters.outputs.num_outputs = 0
model = BinaryQuadraticModel(g)
solver = Solver(client)
result = solver.solve(model)
You can check the execution result by creating a constraint object with g = penalty(f)
and building a logical model.
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(x, values))
[1, 0]
[0, 1]
[0, 0]
As seen in the above result, we were able to obtain all the solutions that satisfy the NAND
condition.
Construction Using Helper Functions¶
If the penalty()
function is used, a penalty function that meets the constraints needs to be manually designed. The Amplify SDK provides the helper functions that create constraint objects for typical constraints.
equal_to()
constrains a given polynomial \(f\) to a constant value \(c\).less_equal()
constrains a given polynomial \(f\) to be less than or equal to a constant value \(c\). However, \(f\) must be a polynomial that takes only integer values, and its range and the constraint range must overlap.greater_equal()
constrains a given polynomial \(f\) to be greater than or equal to a constant value \(c\). However, \(f\) must be a polynomial that takes only integer values, and its range and the constraint range must overlap.clamp()
constrains a given polynomial \(f\) to be greater than or equal to a constant value \(c_1\) and less than or equal to \(c_2\). However, \(f\) must be a polynomial that takes only integer values, and its range and the constraint range must overlap.
Constraint 
Generating function 
Condition for use 


\(f \left( \mathbf{q} \right) = c\) 
\(\exists \mathbf{q}, f\left( \mathbf{q} \right) = c\) 

\(f \left( \mathbf{q} \right) \le c\) 
\(\forall \mathbf{q}, f\left( \mathbf{q} \right) \in \mathbb{Z}\) and \(\exists \mathbf{q}, f\left( \mathbf{q} \right) \le c\) 

\(f \left( \mathbf{q} \right) \ge c\) 
\(\forall \mathbf{q}, f\left( \mathbf{q} \right) \in \mathbb{Z}\) and \(\exists \mathbf{q}, f\left( \mathbf{q} \right) \ge c\) 

\(c_1 \le f \left( \mathbf{q} \right) \le c_2\) 
\(\forall \mathbf{q}, f\left( \mathbf{q} \right) \in \mathbb{Z}\) and \(\exists \mathbf{q}, f\left( \mathbf{q} \right) \le c_2\) and \(\exists \mathbf{q}, f\left( \mathbf{q} \right) \ge c_1\) 
Examples using specific constraints are shown below.
Onehot Constraint¶
One of the typical constraints is the Onehot constraint. For a set of multiple bit variables, only one of them is \(1\) and the others are \(0\).
For example, for the polynomial with \(n\) number of variables, the constraint condition is satisfied only when \(\sum_{i = 0}^{n1} q_i = 1\).
equal_to()
can be used to build the constraint object to express this constraint condition.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 4)
f = equal_to(sum_poly(q), 1)
>>> f
q_0 + q_1 + q_2 + q_3 == 1.000000
In the above, equal_to(sum_poly(q), 1)
sets the polynomial object, where the first argument is the target to be constrained, and the second one is the constant value which the target is constrained to.
We can check the execution result by setting the client and building a logical model from the constraint object as follows:
from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True # Duplicate output of solutions with the same energy value
client.parameters.outputs.num_outputs = 0
model = BinaryQuadraticModel(f)
solver = Solver(client)
result = solver.solve(model)
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(q, values))
[1, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
For the target variable array q
, we got all four solutions where only one of the four variables is \(1\), and the others are \(0\).
Equality Constraint¶
Here, we show the example of the equality constraint, where an arbitrary polynomial is constrained to satisfy \(f \left( \mathbf{q} \right) = c\).
We use equal_to()
in the same way as in the case of the Onehot constraint.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 4)
f = 3 * q[0]  q[1]  2 * q[2] + q[3]
g = equal_to(f, 2)
>>> g
3.000000 q_0  q_1  2.000000 q_2 + q_3 == 2.000000
In the above, equal_to(f, 2)
sets the polynomial object whose first argument is the constraint target and the constant value as the second argument.
We can check the execution result by setting the client and building a logical model from the constraint object as follows.
from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True # Duplicate output of solutions with the same energy value
client.parameters.outputs.num_outputs = 0
model = BinaryQuadraticModel(g)
solver = Solver(client)
result = solver.solve(model)
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(q, values))
[1, 1, 0, 0]
[1, 0, 1, 1]
For the polynomial f
, we now have an array of variables q
that satisfies f = 2
.
Inequality Constraint¶
In this example, we show how to constrain polynomials, which take positive integer values, with inequalities (greater than or equal to, less than or equal to, range).
less_equal()
constrains a given polynomial \(f\) to be less than or equal to a constant value \(c\) (\(f \le c\)) .greater_equal()
constrains a given polynomial \(f\) to be greater than or equal to a value \(c\) (\(f \ge c\)).clamp()
constraints a given polynomial \(f\) to be greater than a constant value \(c_1\) and less than another constant value \(c_2\) (\(c_1 \le f \le c_2\)).
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import less_equal
q = gen_symbols(BinaryPoly, 4)
f = 4 * q[0] + 3 * q[1] + 2 * q[2] + q[3]
g = less_equal(f, 3)
In the above, in order to express the constraint condition for \(f \le 3\), in less_equal(f, 3)
, we set the polynomial object \(f\) to be constrained to the first argument and a constant value to the second argument.
The execution result can be checked in the following way.
from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True # Duplicate output of solutions with the same energy value
client.parameters.outputs.num_outputs = 0
solver = Solver(client)
result = solver.solve(g)
>>> g
4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 <= 3
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(q, values))
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
For the polynomial f
, we now have an array of variables q
that satisfies f <= 3
.
Similarly, when constraining with \(f \ge 3\), use the greater_equal()
function.
from amplify.constraint import greater_equal
g = greater_equal(f, 3)
result = solver.solve(g)
>>> g
4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 >= 3
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(q, values))
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]
Similarly, if we need to introduce the type of constraint where a function takes values in between some constants, such as \(2 \le f \le 3\), we use the clamp()
function. Its first argument is the target to be constrained, and the lower and upper limits are specified by the second and third arguments, respectively.
from amplify.constraint import clamp
g = clamp(f, 2, 3)
result = solver.solve(g)
>>> g
2 <= 4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 <= 3
>>> for solution in result
>>> values = solution.values
>>> print(decode_solution(q, values))
[0, 0, 1, 1]
[0, 0, 1, 0]
[0, 1, 0, 0]
For the polynomial f
, we have an array of variables q
that satisfies 2 <= f <= 3
.
Note
The use of inequality constraints, such as less_equal()
, complicates the formulation of a problem, and it tends to make it more difficult to find solutions because many auxiliary variables are needed.
It should be also noted that the helper functions do not support the constraint conditions by real numbers. In this case, Advanced method for constructing constraint objects may be useful for constructing inequality constraint objects.
Labeling Constraints¶
Constraint objects can be labeled. This allows us to conveniently filter constraints based on the labels. See Solution filtering for the filtering examples.
We can label a constraint object as follows:
from amplify.constraint import (penalty, equal_to)
g1 = penalty(f, "penalty_label")
g2 = equal_to(f, 2, "equal_to_label")
>>> g1
penalty_label: 4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 == 0
>>> g2
equal_to_label: 4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 == 2.000000
The label is displayed along with the constraint expression when printing. Furthermore, the label of a given constraint object can be explicitly checked in the following way.
>>> g1.label
'penalty_label'
Advanced Method for Constructing Constraint Objects¶
Using penalty()
function, we can construct constraint objects with more elaborate settings of penalty functions. Normally, a given penalty function \(g\) takes the values with \(g\geq0\) for all combinations of the available variables, and it takes the minimum value \(g=0\) when the constraint conditions are satisfied. This notion of constraint satisfaction can be modified, and it can be converted to more elaborate conditions using an equality or inequality constraint with an arbitrary constant value.
For instance, when the minimum value of a given penalty function \(g\) is not \(0\), namely \(m\neq0\), we can explicitly specify the minimum value of a penalty function in the following way.
from amplify import BinaryPoly, Solver, decode_solution, gen_symbols
from amplify.constraint import penalty
q = gen_symbols(BinaryPoly, 3)
f = q[0]  0.5 * q[1]  0.5 * q[2] # objective function f
g = q[0] * q[1] + q[1] * q[2] + q[2] * q[0] + 1 # penalty function g (minimum value 1)
p = penalty(g, eq = 1, label = "g = 1") # check constraint satisfaction by g = 1
>>> p
g = 1: q_0 q_1 + q_0 q_2 + q_1 q_2 == 1.000000
In penalty()
function, the penalty function is specified in the first argument. In the second argument, the keyword argument with eq
(equal to) specifies the value of the penalty function at which the constraint is meant to be satisfied. In the above example, the constraint is satisfied when the penalty function \(g\) takes the specified value, namely \(g=1\). In order to label constraints, the label needs to be specified by the keyword argument with label
.
from amplify.client import FixstarsClient
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True # Enable duplicate output for solutions with the same energy values
client.parameters.outputs.num_outputs = 0 # Output all the found solutions
solver = Solver(client)
>>> result = solver.solve(f + p)
>>> for sol in result:
>>> print(f"q = {decode_solution(q, sol.values)}, f = {sol.energy}, g = {g.replace_all(sol.values)}")
q = [1, 0, 0], f = 1.0, g = 1.0
Here, we find the solution where the penalty function evaluates to \(g = 1\).
Inequality can be also used to set constraint conditions. It is used to realize “weaker constraint condition” than the typical constraint conditions meant by penalty functions, or to indirectly realize “inequality constraint condition”. A penalty function usually determines a solution to be feasible when \(g\) takes the minimum value \(m\). This condition can be relaxed so that solutions within a certain range of \(g\) can be considered feasible. This inequality constraint thus allows us to find solutions with smaller value of \(g\) without having to evaluate at its minimum value \(g=m\).
The constraint object with the inequality constraint is given as follows:
q = gen_symbols(BinaryPoly, 3)
f = q[0]  0.5 * q[1]  0.5 * q[2] # Objective function f
g = q[0] * q[1] + q[1] * q[2] + q[2] * q[0] # Penalty function g (minimum value is 0)
p = penalty(g, le = 1, label = "g <= 1") # check constraint satisfaction by g <= 1
>>> p
g <= 1: q_0 q_1 + q_0 q_2 + q_1 q_2 <= 1.000000
The keyword argument expressing inequalities can be specified from le
(less equal), ge
(greater equal), lt
(less than), and gt
(greater than). In the above example, the constraint satisfaction of the penalty function \(g \ge 0\) is checked by \(g \le 1\) (as opposed to \(g = 0\)).
>>> result = solver.solve(f + p)
>>> for sol in result:
>>> print(f"q = {decode_solution(q, sol.values)}, f = {sol.energy}, g = {g.replace_all(sol.values)}")
q = [1, 1, 0], f = 1.5, g = 1.0
q = [1, 0, 1], f = 1.5, g = 1.0
q = [1, 0, 0], f = 1.0, g = 0.0
We were able to find multiple solutions by using the inequality \(g \le 1\) for checking the constraint satisfaction.
Note
When setting a check function for constraint satisfaction, one should be aware of how the penalty function works. For example, if the specified check function has conflicts or contradictions with the meaning of the penalty function in optimization, no feasible solution can be found.
Operators and Methods of Constraint Class¶
How to Check if the Constraints are Met¶
By giving a set of variable values to a constraint object, we can check whether the given variable values can satisfy the constraint condition. The variable values can be given in the forms of a dictionary, list, and function object, but they must be resolvable for all indices of the variables included in the constraint condition.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 4)
f = equal_to(sum_poly(q), 1)
>>> f.is_satisfied({0: 1, 1: 0, 2: 0, 3: 0})
True
>>> f.is_satisfied([0, 1, 0, 0])
True
>>> f.is_satisfied(lambda i: 1 if i == 0 else 0)
True
>>> f.is_satisfied({0: 1, 1: 0, 2: 0, 3: 1})
False
>>> f.is_satisfied([1, 1, 1, 1])
False
>>> f.is_satisfied(lambda i: 0)
False
Obtain Penalty Function¶
We can obtain the penalty function, which is the internal representation of the constraint object, as follows.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to, less_equal
q = gen_symbols(BinaryPoly, 4)
f1 = equal_to(sum_poly(q), 1)
f2 = less_equal(sum_poly(q), 2)
>>> f1.penalty
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_0 q_3 + 2.000000 q_1 q_2 + 2.000000 q_1 q_3 + 2.000000 q_2 q_3  q_0  q_1  q_2  q_3 + 1.000000
If auxiliary variables are required to construct a penalty function, such as the case where a highorder polynomial or an inequality constraint is given, the penalty function cannot be obtained as it is. This is because the indices of the auxiliary variables are uncertain.
>>> f2.penalty
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
RuntimeError: Function to publish ancillary variables is not given
In this case, we can check the penalty function after converting it to a logical model by giving it to BinaryQuadraticModel
etc. However, it should be noted that the indices of the resulting logical model may not coincide with the indices of the input model, because there may be a transformation between the input and the logical variables.
>>> m = BinaryQuadraticModel(f2)
>>> m.input_constraints
[(q_0 + q_1 + q_2 + q_3 <= 2, 1)]
>>> m.input_constraints[0][0].penalty
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_0 q_3  2.000000 q_0 q_4  2.000000 q_0 q_5 + 2.000000 q_1 q_2 + 2.000000 q_1 q_3  2.000000 q_1 q_4  2.000000 q_1 q_5 + 2.000000 q_2 q_3  2.000000 q_2 q_4  2.000000 q_2 q_5  2.000000 q_3 q_4  2.000000 q_3 q_5 + 2.000000 q_4 q_5 + q_0 + q_1 + q_2 + q_3 + q_4 + q_5
Setting the Strength of Constraints¶
The constraint object is supposed to be given to a logical model such as BinaryQuadraticModel
, it is also possible to set its “strength”. “Strength” has no real meaning in the constraint object alone, but when converted to a logical model, it is treated as the relative strength to polynomial objects, matrix classes, and other constraint objects.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 4)
f = 1 * equal_to(sum_poly(q), 1)
>>> f
(q_0 + q_1 + q_2 + q_3 == 1.000000, 1)
A constraint object, whose strength coefficient is set, is represented by a pair of the constraint condition and the strength. The strength coefficient value can be changed later, but the constraint condition by itself cannot be changed.
>>> f[1] = 2
>>> f
(q_0 + q_1 + q_2 + q_3 == 1.000000, 2)
Containerization of Constraints¶
If given to a logical model such as BinaryQuadraticModel
, it is possible to combine multiple constraint objects.
from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 4)
f1 = equal_to(q[0] + q[1], 1)
f2 = 2 * equal_to(q[2] + q[3], 1)
g = f1 + f2
>>> g
[(q_0 + q_1 == 1.000000, 1), (q_2 + q_3 == 1.000000, 2)]
It can be added and containerized without distinguishing whether the strength is set or not. If the strength of a constraint object is not explicitly set, its value is set to 1
as the default value upon containerization.
We can multiply or divide the strength of the entire constraint object container as shown below:
>>> g *= 2
>>> g
[(q_0 + q_1 == 1.000000, 2), (q_2 + q_3 == 1.000000, 4)]
Note
Please refer Adjusting Constraint Strength for an example of containerization and strength settings for specific constraints.
Multiplication and Division Operators¶
Multiplication and division on the constraint objects can also change the coefficient values of the strength of the constraints.
The relations between the multiplication/division targets and the return values are as follows:
Coefficient type 
Multiplication/division target class 
Return class 

int 

float 

Addition Operator¶
The addition of constraint objects change their behaviors depending on the target to which they are added. If the target of addition is a polynomial object or a matrix object, a logical model is built. On the other hand, if the target of addition is a constraint object, a constraint container is built.
The relations between the addition targets and the return values are as follows:
Constraint class 
Addition target class 
Return class 
