# 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:

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$$

penalty()

$$\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 (
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

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$$

equal_to()

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

$$f \left( \mathbf{q} \right) \le c$$

less_equal()

$$\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$$

greater_equal()

$$\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$$

clamp()

$$\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.

### One-hot Constraint¶

One of the typical constraints is the One-hot 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}^{n-1} 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

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 One-hot 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

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 high-order 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: