Quadratic Assignment Problem¶
Quadratic assignment problem (QAP) is the following problem.
Let \(N\) be a positive integer. Consider \(N\) factories to be built on \(N\) candidate sites. Each factory can be built on any of the candidate sites. Every two factories have trucks traveling to and from them, and their transportation volumes are known in advance. How can we minimize the sum of the amount transported x the distance traveled?
An application could be to determine the seating chart for a meeting so that people close to each other have seats closely.
Formulation¶
Let \(N\) potential factory locations be denoted by land \(0\), land \(1\), … , and \(N\) factories are denoted as factories \(0\), factories \(1\), …, factories \(N-1\). Also let \(D_{i, j}\) denote the distance between land \(i\) and land \(j\), and \(F_{k, l}\) denote the transport volume between factory \(k\) and factory \(l\).
Variables¶
With \(N \times N\) binary variables \(q\), let \(q_{i, k}\) represent whether factory \(k\) is to be built on land \(i\).
For example, factory \(3\) will be built on land \(0\) if \(q\) has the following value.
factory 0 |
factory 1 |
factory 2 |
factory 3 |
factory 4 |
|
---|---|---|---|---|---|
land 0 |
0 |
0 |
0 |
1 |
0 |
land 1 |
0 |
1 |
0 |
0 |
0 |
land 2 |
0 |
0 |
0 |
0 |
1 |
land 3 |
1 |
0 |
0 |
0 |
0 |
land 4 |
0 |
0 |
1 |
0 |
0 |
Constraints¶
Each row and column of the binary variable table must have exactly one variable that is 1, so we place a one-hot constraint on each row and column. Conversely, if these are satisfied, then there is only one way to determine which factory to build on which land.
Objective function¶
The objective function is the sum of transport volume x distance between factories. This can be expressed in the equation using \(q\) as follows.
Formulation¶
The above formulation, with \(N\times N\) binary variables \(q\), can be written as follows.
Problem setting¶
Before formulating with the Amplify SDK, we will create a problem. For simplicity, let the number of factories \(N=10\).
import numpy as np
N = 10
Next, we create a distance matrix \(D\) representing the distances between lands. The lands are randomly generated on the Euclidean plane. The distance matrix distance
is created as a two-dimensional numpy.ndarray
.
rng = np.random.default_rng()
x = rng.integers(0, 100, size=(N,))
y = rng.integers(0, 100, size=(N,))
distance = (
(x[:, np.newaxis] - x[np.newaxis, :]) ** 2
+ (y[:, np.newaxis] - y[np.newaxis, :]) ** 2
) ** 0.5
print(distance)
[[ 0. 14.56 72.422 14.866 80.156 14.036 81.043 21.471 34. 80.654]
[14.56 0. 84.929 20.125 90.338 28.16 82.292 35.847 39.699 82.298]
[72.422 84.929 0. 82.292 22.091 58.873 73.11 59.363 53.6 71.063]
[14.866 20.125 82.292 0. 92.455 24.207 95.88 24.331 48.754 95.509]
[80.156 90.338 22.091 92.455 0. 68.25 56.4 72.25 52.887 54.203]
[14.036 28.16 58.873 24.207 68.25 0. 77.414 12.083 29.069 76.655]
[81.043 82.292 73.11 95.88 56.4 77.414 0. 88.051 48.374 2.236]
[21.471 35.847 59.363 24.331 72.25 12.083 88.051 0. 40.112 87.144]
[34. 39.699 53.6 48.754 52.887 29.069 48.374 40.112 0. 47.676]
[80.654 82.298 71.063 95.509 54.203 76.655 2.236 87.144 47.676 0. ]]
Also, we create a matrix \(F\) representing the amount of transport between factories, a random symmetric matrix of dimension 2, named flow
.
flow = np.zeros((N, N), dtype=int)
for i in range(N):
for j in range(i + 1, N):
flow[i, j] = flow[j, i] = rng.integers(0, 100)
print(flow)
[[ 0 99 97 31 78 50 23 16 7 86]
[99 0 86 55 94 1 95 63 38 48]
[97 86 0 43 68 54 33 32 25 35]
[31 55 43 0 92 69 54 67 11 56]
[78 94 68 92 0 37 8 44 10 45]
[50 1 54 69 37 0 1 74 79 26]
[23 95 33 54 8 1 0 88 20 79]
[16 63 32 67 44 74 88 0 38 7]
[ 7 38 25 11 10 79 20 38 0 39]
[86 48 35 56 45 26 79 7 39 0]]
Formulation with the Amplify SDK¶
In the formulation, we can use the Matrix
class for efficient formulation, since a quadratic term consisting of any two binary variables can appear in the objective function.
Creating variables¶
To formulate using the Matrix
class, VariableGenerator
’s matrix()
method to issue variables.
from amplify import VariableGenerator
gen = VariableGenerator()
matrix = gen.matrix("Binary", N, N) # coefficient matrix
q = matrix.variable_array # variables
q
Creating the objective function¶
The matrix
created above is an instance of the class Matrix
, which has the following three properties.
quadratic
is numpy.ndarray
representing the coefficients of the second order terms, and its shape
is (N, N, N, N)
this time. quadratic[i, k, j, l]
corresponds to the coefficients of q[i, k] * q[j, l]
. That is, quadratic
must be set to a 4-dimensional NumPy array such that quadratic[i, k, j, l] = distance[i, j] * flow[k, l]
linear
and constant
represent the coefficient and constant terms of the linear term, respectively, but since the objective function used in this problem contains only second order terms, we will not set them.
np.einsum("ij,kl->ikjl", distance, flow, out=matrix.quadratic)
Creating constraints¶
Impose a one-hot constraint on each row and column of the variable array q
created in [](#Creating variables).
from amplify import one_hot
constraints = one_hot(q, axis=1) + one_hot(q, axis=0)
Creating a combinatorial optimization model¶
Let’s combine the objective function and constraints to create a model.
penalty_weight = np.max(distance) * np.max(flow) * (N - 1)
model = matrix + penalty_weight * constraints
The penalty_weight
is applied to the constraints to give weight to the constraints. In Amplify AE, the solver used in this example, if you do not specify appropriate weights for the constraints, the solver will search in the direction of making the objective function smaller rather than trying to satisfy the constraints, and you will not be able to find a feasible solution. See Constraints and Penalty Functions for details.
Creating a solver client¶
Now, we will create a solver client to perform combinatorial optimization using Amplify AE. The solver client class corresponding to Amplify AE is FixstarsClient
class.
from amplify import FixstarsClient
client = FixstarsClient()
We also need to set the API token required to run Amplify AE.
Tip
After user registration, you can obtain a free API token that can be used for evaluation and validation purposes.
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
We will set the solver’s timeout.
import datetime
client.parameters.timeout = datetime.timedelta(seconds=1)
Executing the solver¶
Finally, we will execute the solver using the created combinatorial optimization model and the solver client to find the solution to the quadratic programming problem.
from amplify import solve
result = solve(model, client)
The objective function value based on the best solution is shown below.
result.best.objective
196225.08008822126
The values of the variables in the optimal solution can be obtained in the form of a NumPy multidimensional array as follows.
q_values = q.evaluate(result.best.values)
print(q_values)
[[0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
[1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
[0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
[0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]]
Checking the results¶
We will visualize the results using matplotlib.
import itertools
import matplotlib.pyplot as plt
plt.scatter(x, y)
factory_indices = (q_values @ np.arange(N)).astype(int)
for i, j in itertools.combinations(range(N), 2):
plt.plot(
[x[i], x[j]],
[y[i], y[j]],
c="b",
alpha=flow[factory_indices[i], factory_indices[j]] / 100,
)
