4. Constructing Constraints¶

Constraints are the conditions that must be satisfied by the values of the decision variables in a combinatorial optimization problem. In the Amplify SDK you can set constraints on the range of possible values for each variable and constraints on the range of possible values for polynomial expressions.

This page explains how to set constraints on decision variables and construct constraint objects using polynomials.

4.1. Fixing variable values¶

In some cases, you may want to fix the values of decision variables, such as when the values of some decision variables are pre-determined in a formulation. By replacing part of the variable array with numeric values in advance, as follows, you can effectively fix the values of the variables.

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))

q[0, :] = 0
q[:, 0] = 0
q[0, 0] = 1

Alternative

The above implementation of assigning numeric values to q can also be written as follows, with the same effect. However, the above implementation is generally computationally efficient.

for i in range(3):
    q[i, 0] = 0
for j in range(3):
    q[0, j] = 0
q[0, 0] = 1

>>> print(q)
[[      1,       0,       0],
 [      0, q_{1,1}, q_{1,2}],
 [      0, q_{2,1}, q_{2,2}]]

We can then construct a polynomial with the value of the fixed variable by using q

>>> p = q.sum()
>>> print(p)
q_{1,1} + q_{1,2} + q_{2,1} + q_{2,2} + 1

You can also impose a constraint where a polynomial with another variable represents a variable by replacing the array of variables with a polynomial. For example, to express the constraint where \(q_{1, 1} = q_{2, 2}\), you can do so as follows.

>>> q[2, 2] = q[1, 1]
>>> print(q)
[[      1,       0,       0],
 [      0, q_{1,1}, q_{1,2}],
 [      0, q_{2,1}, q_{1,1}]]

Tip

If you want to reuse the original variable array q later, you can use copy.

gen = VariableGenerator()
q_org = gen.array("Binary", shape=(3, 3))
q = q_org.copy()

q[0, :] = 0
q[:, 0] = 0
q[0, 0] = 1

>>> print(q_org)
[[q_{0,0}, q_{0,1}, q_{0,2}],
 [q_{1,0}, q_{1,1}, q_{1,2}],
 [q_{2,0}, q_{2,1}, q_{2,2}]]

4.2. Setting the range of variable values¶

For integer and real variables, you can set the range of possible values for a variable with float or None, where None indicates that the variable is unbounded.

To set the bounds of a variable at issuance, set the bounds parameter of the scalar(), array(), and matrix() methods to the bounds of the variable.

>>> n = gen.array("Integer", shape=(5,), bounds=(1, 3))
>>> print(n[0].as_variable())
{name: n_0, id: 9, type: Integer, lower_bound: 1, upper_bound: 3}

To specify a range for an individual variable, specify it in the lower_bound and upper_bound attributes.

>>> n[0].lower_bound = 0
>>> n[0].upper_bound = None
>>> print(n[0].as_variable())
{name: n_0, id: 9, type: Integer, lower_bound: 0, upper_bound: inf}

4.3. Setting the range of polynomial values¶

The Amplify SDK manages equality, inequality, and other expressions representing constraints on the range of possible polynomial values as constraint objects of the Constraint class. By using constraint objects, the Amplify SDK can extract solutions that satisfy the constraints from the results from the machine or solver. If the constraints are not satisfied, the Amplify SDK can determine which constraints were not satisfied.

The constraint object also provides the ability to generate penalty functions for solvers that cannot directly handle constraint conditions, such as the QUBO solver. A penalty function is a polynomial computed for each constraint condition when a constrained combinatorial optimization problem is converted to an unconstrained problem using a penalty method.

The helper functions provided for each constraint type help construct constraints. It automatically analyzes the constraint expressions and generates an optimized penalty function.

Note

Even when you do not need to generate penalty functions, please use the helper functions, as they have no downside.

4.3.1. Equality constraints¶

You can use the following helper functions to create constraint objects that represent equality.

Helper function	Effect
`equal_to()`	Constrains the polynomial to be equal to the right-hand side.
`one_hot()`	Constrains the polynomial to be equal to 1.

To impose a constraint on a polynomial with equality, use the equal_to() function. The following example creates a constraint object imposing \(q_{0,0} + q_{1,1} + q_{2,2} = 1\) for a two-dimensional array of variables \(q\).

from amplify import VariableGenerator, equal_to, one_hot

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))
c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1)

>>> print(c)
q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)

You can put labels on constraints. The labels are helpful for identification when later reviewing the results of the constraint evaluation. You can change them at a later time.

>>> c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1, label="diagonal sum")
>>> print(c)
diagonal sum: q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)
>>> c.label = "diagonal sum (I should give a long name to this!)"
>>> print(c)
diagonal sum (I should give a long name to this!): q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)

Passing a polynomial array PolyArray to the helper function constrains the sum of the array elements.

>>> c = equal_to(q[0], 1, label="1st row sum")
>>> print(c)
1st row sum: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1)

This is equivalent to the below implementation.

c = equal_to(q[0].sum(), 1, label="1st row sum")

The one_hot() function creates an equality constraint whose right-hand side is 1. Otherwise, it is the same as the equal_to() function.

>>> c = one_hot(q[0], label="1st row one-hot")
>>> print(c)
1st row one-hot: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1)

This is equivalent to the below implementation.

c = equal_to(q[0], 1, label="1st row one-hot")

Note

Equality constraints on polynomials containing real variables and real coefficients are subject to numerical errors, which can lead to an incorrect decision of satisfaction.

In particular, solvers that cannot handle real variables, such as the QUBO solver, may not be able to express equality constraints correctly because they convert real variables to a small number of binary variables (see “Conversion from real to binary variables” for conversion from real to binary variables).

In such cases, consider expressing inequality constraints with an acceptable error instead of equality constraints.

4.3.2. Inequality constraints¶

You can use the following helper functions to create constraint objects representing inequalities.

Helper function	Effect
`less_equal()`	Constrains a polynomial to be less than or equal to the right-hand side.
`greater_equal()`	Constrains a polynomial to be greater than or equal to the right-hand side.
`clamp()`	Constrains the polynomial to be in a range between.

less_equal() and greater_equal() are similar to equal_to() in that the first argument is a polynomial or polynomial array, and the second argument is the right-hand side value.

from amplify import less_equal, greater_equal

c_le = less_equal(q[0], 2)
c_ge = greater_equal(q[0], 2)

>>> print(c_le)
q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)
>>> print(c_ge)
q_{0,0} + q_{0,1} + q_{0,2} >= 2 (weight: 1)

clamp() constrains the polynomial to a range. The range is specified as a tuple.

from amplify import clamp

c_bw = clamp(q[0], (1, 2))

>>> print(c_bw)
1 <= q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)

If the lower and upper bounds of the range are equal, it is treated as an equality constraint.

>>> c_bw = clamp(q[0], (2, 2))
>>> print(c_bw)
q_{0,0} + q_{0,1} + q_{0,2} == 2 (weight: 1)

This is equivalent to the below implementation.

c_bw = equal_to(q[0], 2)

If the lower or upper bound is None, this is equivalent to less_equal() or greater_equal(), respectively.

>>> c_le = clamp(q[0], (None, 2))
>>> print(c_le)
q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)

>>> c_ge = clamp(q[0], (2, None))
>>> print(c_ge)
q_{0,0} + q_{0,1} + q_{0,2} >= 2 (weight: 1)

Attention

The generation of penalty functions for inequality constraints for the QUBO solver requires auxiliary variables that may be inefficient or impossible to formulate rigorously. See “Inequality constraints” for details.

4.3.3. Constraint list¶

You can use a constraint list ConstraintList to handle multiple constraints. You can add constraint objects Constraint together to form a constraint list.

from amplify import VariableGenerator, equal_to

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))

>>> c0 = equal_to(q[0], 1)
>>> c1 = equal_to(q[1], 1)
>>> clist = c0 + c1
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)]

You can also add constraint objects with the + or += operator after creating the ConstraintList.

>>> clist += equal_to(q[2], 1)
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1),
 q_{2,0} + q_{2,1} + q_{2,2} == 1 (weight: 1)]

You can create multiple constraint objects at once for an array of polynomials. When you pass the axis parameter to the helper function, it calculates the sums along the axes of the polynomial array and creates a constraint object for each result.

The following example creates a constraint list ConstraintList so that each row equals 1. If a label is given, the specified string is automatically followed by a number.

>>> clist = equal_to(q, 1, axis=1, label="row sum")
>>> print(clist)
[row sum0: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 row sum1: q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1),
 row sum2: q_{2,0} + q_{2,1} + q_{2,2} == 1 (weight: 1)]

Hint

It is efficient to batch-create constraints using the axis parameter whenever possible.

4.3.4. Setting constraint weights¶

You can give a weight to the constraint object Constraint created using the equal_to() or less_equal() functions. The weight parameter is mainly helpful for the QUBO solver or the Ising solver, and the larger the weight, the more likely it is to find a solution that satisfies the constraint. However, if the constraint weights are too large, finding solutions with small objective function values tends to be more challenging.

4.3.5. Domain wall constraints¶

The Amplify SDK supports the creation of some special constraints with helper functions.

Note

In most cases, using the functions described above to create equality and inequality constraints is sufficient. The functions described below should be used by those who need to formulate special constraints.

A domain wall constraint forces a one-dimensional binary or Ising variable array to have 0 (-1 for Ising variables) for more than or equal to 0 times, followed by 1 for more than or equal to 0 times from the left. For example, for the binary variable array q = [q_0, q_1, q_2, q_3], q = [0, 0, 0, 0] or q = [0, 1, 1, 1] would satisfy the constraint, but q = [0, 1, 1, 0] would not.

To create a domain wall constraint, pass an array of variables to the domain_wall() function.

from amplify import domain_wall

gen = VariableGenerator()
q = gen.array("Binary", 4)
dw = domain_wall(q)

For a binary variable array, the constraint expression for the domain wall constraint is:

\[\sum_{i=0}^{n-2} q_i - q_i q_{i+1} = 0.\]

The above equation can be interpreted as a constraint where the number of variables that vary from \(1 \rightarrow 0\) between adjacent variables is 0. In program code, you can see this as follows.

>>> print(dw)
- q_0 q_1 - q_1 q_2 - q_2 q_3 + q_0 + q_1 + q_2 == 0 (weight: 1)

Note

Although the constraint equation for a domain wall constraint is expressed as an equality expression, the constraint constructed by passing both sides of this constraint equation to the equal_to() function is not equivalent to the constraint constructed using the domain_wall() function. The difference is because the penalty function generated by the constraint differs, and the constraint constructed using the domain_wall() function is more efficient. See “Constraints and Penalty Functions” for more information about penalty functions.

In the case of an Ising variable array, a constraint is generated where the number of variables changing between adjacent variables \(+1 \rightarrow -1\) is 0.

gen = VariableGenerator()
s = gen.array("Ising", 4)
dw = domain_wall(s)

The expression of the constraint condition is:

\[\frac{1}{4} \sum_{i=0}^{n-2} s_i - s_{i + 1} - s_i s_{i+1} = 0.\]

You can check this as follows.

>>> print(dw)
- 0.25 s_0 s_1 - 0.25 s_1 s_2 - 0.25 s_2 s_3 + 0.25 s_0 - 0.25 s_3 + 0.75 == 0 (weight: 1)

Tip

To reverse the direction of the value change, set the ascending parameter of the domain_wall() function to False. In this case, for the binary variable array q = [q_0, q_1, q_2, q_3], q = [0, 0, 0, 0] or q = [1, 1, 1, 0] would satisfy the constraint, but q = [0, 0, 1, 1] would not.