This website uses cookies to improve your user experience on this site. By continuing to view
this site, you agree to our group's privacy
policy 
.
Run on Jupyter Notebook
TutorialIn the optimization problems that we have dealt with so far in this tutorial, there is no limit to the values that the decision variables can take, and we searched for the value that minimizes the objective function among all possible combinations of values that the decision variables can take.
However, in a general optimization problem, there are cases where optimal solutions must be sought from the decision variables satisfying certain conditions. This kind of problem is called a constrained optimization problem.
The following is an example of a constrained optimization problem:
In addition to the inequality constraints mentioned above, there are other examples such as the following:
When constraints are imposed, it is necessary to find the optimal solution from the "feasible solutions" that satisfy the constraints.
However, the QUBO and Ising models cannot handle constraints. Therefore, when solving constrained optimization problems by attributing them to QUBO, it is necessary to express the constraints as parts of the objective function.
The basic approach is to add a penalty function $g$ to the original objective function $f$ with weights such that it takes the minimum value if the constraints are satisfied. By finding the optimal solution for $h = f + \lambda g\quad (\lambda \gt 0)$ instead of $f$, it is possible to obtain a feasible solution that minimizes the penalty function $g$, i.e., satisfies the constraints. In practice, the obtained solution is not necessarily the optimal solution, so we identify whether it is a feasible solution by checking if the solution of $h$ is the minimum value when evaluated with $g$.
For example, this equality constraint can be expressed using the following penalty function
$x_1 + x_2 = 1$
$g(\mathbf{x}) = (x_1 + x_2 - 1)^2$
This function will only be $g(\mathbf{x}) = 0$ if $x_1 + x_2 = 1$, otherwise it will take a positive value $g(\mathbf{x}) > 0$.
We need to consider such a penalty function for each constraint, and Amplify can automatically add the above constraints (inequality constraints, equality constraints, and logic equation constraints) as penalty functions to the objective function.
In Amplify, typical constraints are abstracted in the form of constraint objects, aside from objective functions.
Using the constraint object provides the following advantages:
The most primitive constraint object is the one created by the penalty function.
The penalty function creates a constraint object $g$ that represents the constraint
$f(\mathbf
x)=0$ on the variable $\mathbf x$.
However, the penalty function has an applicability condition.
In order to use the penalty function, the following must be true:
We check the behavior of the penalty function representing the constraint. The constraints between the decision variables q can be expressed by setting the penalty function g(q) appropriately. g(q) is a function that takes the minimum value when q satisfying the constraint is input. When q that does not satisfy the constraints is input, a "penalty" is imposed such that the function takes a value larger than the minimum value, so $g(\mathbf{q})$ is called a penalty function. Now, as an example of a penalty function using the QUBO variable $q_i = \{0,1\}$, we will show an example of designing a penalty function that makes a decision to satisfy each constraint condition in NAND and OR constraints.
Given two binary variables $q_i, q_j \in \{0, 1\}$, the condition that [both $q_i, q_j$ can never be 1] is called a NAND constraint. The penalty function $g_{\mathrm{NAND}}$, which expresses the NAND constraint, must satisfy the following conditions:
Let's say that the value of $g_{\mathrm{NAND}}$ is 0 when the condition is satisfied, and the value when the condition is not satisfied is 1. Then, the value of $g_{\mathrm{NAND}}$ will be as shown in the following table.
| q_i | q_j | g_NAND(q_i q_j) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
If we set $g_{\rm NAND}(q_i, q_j) = q_i q_j$, we get a function that satisfies the above table.
If $(q_i, q_j)$ satisfies the constraint, then $g_{\rm NAND}(0, 0) = g_{\rm NAND}(0, 1) = g_{\rm NAND}(1, 0) = 0$, which is the minimum value, but if the constraint is not satisfied, then $g_{ m NAND}(1, 1) = 1$. However, if the constraint is not satisfied, $g_{\rm NAND}(1, 1) = 1$ and a penalty is imposed.
Amplify allows you to do the following:
# Importing constraint related
from amplify.constraint import clamp, equal_to, greater_equal, less_equal, penalty
from amplify import (
gen_symbols,
BinaryPoly,
sum_poly,
Solver,
decode_solution,
)
from amplify.client import FixstarsClient
# Set up the client
client = FixstarsClient() # Fistars Optigan
client.url = "http://optigan.fixstars.com"
client.parameters.timeout = 1000 # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.outputs.duplicate = (
True # Output solutions with identical energy values
)
client.parameters.outputs.num_outputs = 0 # 0: Output all solutions found
solver = Solver(client) # Set up a solver
# Binary variable
q = gen_symbols(BinaryPoly, 2)
# Polynomials giving NAND constraints
g_NAND = q[0] * q[1]
# Convert polynomials to penalty constraints
p_NAND = penalty(g_NAND)
print(f"p_NAND = {p_NAND}")
Let's try to find a solution that satisfies the NAND constraint.
# Find a solution that satisfies the NAND constraint
result = solver.solve(p_NAND)
for sol in result:
energy = sol.energy
values = sol.values
print(f"energy = {energy}, {q} = {decode_solution(q, values)}")
Given two binary variables $q_i, q_j \in \{0, 1\}$, the condition that [one of $q_i, q_j$ is 1] is called an OR constraint. The penalty function $g_{\mathrm{OR}}$ expressing the OR constraint satisfies the following conditions:
Let's say that the value of $g_{\mathrm{OR}}$ when the condition is satisfied is 0, and the value when the condition is not satisfied is 1. Then, the value of $g_{\mathrm{OR}}$ will be as shown in the table below.
| q_i | q_j | OR (q_i, q_j) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
If we define $g_{\rm OR}(q_i,q_j) = q_i q_j − q_i − q_j + 1$, we can get a function that satisfies the above table.
If $(q_i, q_j)$ satisfies the constraint, then $g_{\rm OR}(1, 1) = g_{\rm OR}(0, 1) = g_{\rm OR}(1, 0) = 0$, which is the minimum value, but if it does not, then $g_{\rm OR} (0,0) = 1$, which imposes a penalty.
Amplify allows you to do the following:
# Binary variable
q = gen_symbols(BinaryPoly, 2)
# Polynomial that gives OR constraint
g_OR = q[0] * q[1] - q[0] - q[1] + 1
p_OR = penalty(g_OR)
print(f"p_OR = {p_OR}")
Let's actually try to find a solution that satisfies the OR constraint.
# Find a solution that satisfies the OR constraint
result = solver.solve(p_OR)
for sol in result:
energy = sol.energy
values = sol.values
print(f"energy = {energy}, {q} = {decode_solution(q, values)}")
In this section, we explain equality constraints.
Given a function $k(\mathbf{x})$ with variables $\mathbf{x}=x_0, x_1,\cdots$, it may be necessary to constrain the value of this function to a constant value $c$, as in $k(\mathbf{x}) = c$.
Such an equality constraint can be expressed by a penalty function $g$ as follows:
$$ g(\mathbf{x}) = \left(k(\mathbf{x}) - c\right)^2 $$If $\mathbf{x}$ satisfies the constraint, the penalty function is $g(\mathbf{x})=0$ and takes the minimum value. If $\mathbf{x}$ does not satisfy the constraint condition, the penalty function will be greater than $0$ and a penalty will be imposed. Therefore, if the penalty function has a minimum value of $0$, the equality constraint is satisfied, and if it takes other values, the constraint is not satisfied.
As an example of equality constraints, we introduce the one-hot constraint.
Given $N$ binary variables $q_0, q_1, \cdots, q_{N-1}$, we may want to impose a constraint such that only one of these variables will be $1$ and all others will be $0$. Such a constraint is called a one-hot constraint and can be expressed as the following equation:
$$ \sum_{i=0}^{N-1}q_i = q_0 + q_1 + \cdots + q_{N-1} = 1 $$The penalty function for this constraint is the following, which takes a minimum value of $0$ if the constraint condition is satisfied, and a positive value otherwise.
$$ g(\mathbf{q}) = \left(\sum_{i=0}^{N-1}q_i - 1\right)^2 $$In the following, we will show how to implement and check the penalty function for the one-hot constraint when there are three binary variables.
By running a program that imposes the constraint $q_0 + q_1 + q_2 = 1$ on the three binary variables $q_0, q_1, q_2$, we can confirm the following:
$$ (q_0, q_1, q_2) = (0, 0, 1),\, (0, 1, 0),\, (1, 0, 0) $$from amplify import (
gen_symbols,
BinaryPoly,
sum_poly,
Solver,
decode_solution,
)
from amplify.client import FixstarsClient
q = gen_symbols(BinaryPoly, 3) # Generate 4 binary variables
g = (sum_poly(q) - 1) ** 2 # Penalty function for one-hot constraints
solver = Solver(client) # Set up a solver
# Solve a problem and view the results
result = solver.solve(g)
for sol in result:
energy = sol.energy
values = sol.values
print(f"energy = {energy}, {q} = {decode_solution(q, values)}")
Consider creating three binary variables $\mathbf{q} = (q_0, q_1, q_2)$ and imposing the following equality constraint between these variables:
$$ q_0 q_1 + q_2 = 1 $$Amplify can create objects for equality constraints using the equal_to function. Unlike
penalty, the equal_to function has no restrictions on the range or minimum
value
of the function in question (we recommend using the penalty function when available, due to
the
complexity of the formulation).
With this constraint, we can confirm that we get the following four solutions by running the following source code:
$$ (q_0, q_1, q_2) = (1, 1, 0),\, (1, 0, 1),\, (0, 0, 1),\, (0, 1, 1) $$Here, it is useful to use the sum_poly function provided by Amplify to sum the
variables.
from amplify import (
gen_symbols,
BinaryPoly,
sum_poly,
Solver,
decode_solution,
)
from amplify.client import FixstarsClient
from amplify.constraint import equal_to
q = gen_symbols(BinaryPoly, 3) # Generate three binary variables
g = equal_to(q[0] * q[1] + q[2], 1) # Equality constraint
print(f"g: {g}") # Show constraints
# Set up the client
client = FixstarsClient() # Fistars Optigan
client.url = "http://optigan.fixstars.com"
client.parameters.timeout = 1000 # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.outputs.duplicate = (
True # Output solutions with identical energy values
)
client.parameters.outputs.num_outputs = 0 # 0: Output all solutions found
solver = Solver(client) # Define a solver from a pre-configured client
result = solver.solve(g) # Solve for the given constraints
# Show the results
for sol in result:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
With Amplify, you can set constraints on the size of integer-valued polynomials and integer constants.
For integer-valued polynomials $f$ and integer constants $c$,$c_1$,$c_2$, the table below shows the inequality constraints that can be used with Amplify and the functions that generate the corresponding constraint objects.
| Constraint | Function |
|---|---|
| f(q) ≦ c | less_equal(f,c) |
| f(q) ≧ c | greater_equal(f,c) |
| c_1 ≦ f(q) ≦ c_2 | clamp(f, c_1, c_2) |
less_equal¶Consider generating three QUBO variables $\mathbf{q} = (q_0, q_1, q_2)$ and imposing the following inequality constraints between these variables:
$ q_0 + q_1 + q_2 \leq 1 $
The less_equal function can be used to create objects for inequality constraints.
from amplify import sum_poly, gen_symbols, BinaryPoly, decode_solution
from amplify.constraint import less_equal
q = gen_symbols(BinaryPoly, 3) # Generate three QUBO variables
g2 = less_equal(sum_poly(q), 1) # Inequality constraints
print(f"g2: {g2}") # Show constraints
solver = Solver(client) # Define a solver from a pre-configured client
result = solver.solve(g2) # Solve for the given constraints
for sol in result:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
With this constraint, we can confirm that we get the following four solutions by executing the above source code:
$ (q_0, q_1, q_2) = (0, 0, 0),\,(0, 0, 1),\, (0, 1, 0),\, (1, 0, 0) $
greater_equal¶Consider generating three QUBO variables $\mathbf{q} = (q_0, q_1, q_2)$ and imposing the following inequality constraints between these variables.
$ q_0 + q_1 + q_2 \ge 2 $
We can use the greater_equal function to generate objects for the inequality constraints.
from amplify import sum_poly, gen_symbols, BinaryPoly, decode_solution
from amplify.constraint import greater_equal
q = gen_symbols(BinaryPoly, 3) # Generate three QUBO variables
g2 = greater_equal(sum_poly(q), 2) # Inequality constraints
print(f"g2: {g2}") # Show constraints
solver = Solver(client) # Define a solver from a pre-configured client
result = solver.solve(g2) # Solve for the given constraints
for sol in result:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
With this constraint, we can confirm that we get the following four solutions by executing the above source code:
$ (q_0, q_1, q_2) = (1, 1, 1),\,(0, 1, 1),\, (1, 1, 0),\, (1, 0, 1) $
clamp¶Consider generating three QUBO variables $\mathbf{q} = (q_0, q_1, q_2)$ and imposing the following inequality constraints between these variables:
$ 1 \le q_0 + q_1 + q_2 \le 2 $
The clamp function can be used to generate objects for the inequality constraints.
from amplify import sum_poly, gen_symbols, BinaryPoly, decode_solution
from amplify.constraint import clamp
q = gen_symbols(BinaryPoly, 3) # Generate three QUBO variables
g2 = clamp(sum_poly(q), 1, 2) # Inequality constraints
print(f"g2: {g2}") # Show constraints
solver = Solver(client) # Define a solver from a pre-configured client
result = solver.solve(g2) # Solve for the given constraints
for sol in result:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
With this constraint, we can confirm that we get the following six solutions by executing the above source code:
$ (q_0, q_1, q_2) = (0, 0, 1),\, (0, 1, 0),\, (1, 0, 0),\,(0, 1, 1),\, (1, 1, 0),\, (1, 0, 1) $
q = gen_symbols(BinaryPoly, 2)
g1 = penalty(q[0])
g2 = penalty(q[1])
print(f"g1 + g2 : {g1 + g2}")
The size of the penalty value that a constraint object brings can be adjusted by multiplying it by a scalar.
q = gen_symbols(BinaryPoly, 1)
g = penalty(q[0])
print(f"g : {g}")
# Doubling the weight of constraints
g_2 = 2 * g
print(f"g_2 : {g_2}")
In the above example, $g(q) = 1$ when $q_0 = 1$, and $g(q) = 0$ when $q_0 = 0$.
By setting g_2 = 2 * g, we get $g_2(q) = 2$ when $q_0 = 1$ and $g_2(q) = 0$ when $q_0 =
0$.
By adding constraints to the objective function, we can generate a model that represents a constrained optimization problem.
As an example, let's consider the following constrained optimization problem.
Without the constraint condition, $(q_0,q_1) = (0,0)$ is the optimal solution, but by adding the constraint condition, the solution changes to $(q_0,q_1) = (0,1)$.
q = gen_symbols("Binary", 2)
# Objective function
g = 2 * q[0] + q[1]
# Constraint
p = penalty(q[0] * q[1] - q[0] - q[1] + 1)
# Constrained optimization problem
model = g + p
solver = Solver(client) # Define a solver from a pre-configured client
result_cost_only = solver.solve(g) # Solve an unconstrained optimization problem
print("Solution of an unconstrained optimization problem")
for sol in result_cost_only:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
result = solver.solve(model) # Solve a constrained optimization problem
print("Solution of a constrained optimization problem")
for sol in result:
print(f"energy = {sol.energy}, {q} = {decode_solution(q, sol.values)}")
