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 predetermined 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.
See also
See the βConstraints and Penalty Functionsβ section for details on the generated penalty functions and how to adjust their weights. See also βSpecifying a penalty functionβ for information on specifying your penalty functions without using helper functions.
4.3.1. Equality constraints#
You can use the following helper functions to create constraint objects that represent equality.
Helper function 
Effect 

Constrains the polynomial to be equal to the righthand side. 

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 twodimensional 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 righthand side is 1. Otherwise, it is the same as the equal_to()
function.
>>> c = one_hot(q[0], label="1st row onehot")
>>> print(c)
1st row onehot: 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 onehot")
4.3.2. Inequality constraints#
You can use the following helper functions to create constraint objects representing inequalities.
Helper function 
Effect 

Constrains a polynomial to be less than or equal to the righthand side. 

Constrains a polynomial to be greater than or equal to the righthand side. 

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 righthand 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 batchcreate 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.
See also
Setting a constraint weight is necessary when using a solver that expresses constraints using a penalty function. See βPenalty function weightβ for information about penalty functions and how to adjust the weights.
You can obtain and set the weight of a constraint using the weight
property. The default value is 1.
from amplify import VariableGenerator, equal_to
gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))
c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1)
>>> c.weight
1.0
>>> c.weight = 3
>>> c.weight
3.0
Multiplying a constraint object by a number multiplies its weight.
>>> c.weight
3.0
>>> c *= 2
>>> c.weight
6.0
Multiplication by numbers for weight is also defined for constraint list ConstraintList
objects.
c1 = equal_to(q[0], 1)
c2 = equal_to(q[1], 1)
clist = c1 + c2
>>> 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)]
>>> clist *= 2
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 2),
q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 2)]
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 onedimensional 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:
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:
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.