Source code for eqc_models.assignment.qap

# (C) Quantum Computing Inc., 2024.
import numpy as np
from eqc_models.base import ConstrainedQuadraticModel

[docs] class QAPModel(ConstrainedQuadraticModel): """ Parameters ---------- A : np.array matrix of distances or costs between locations B : np.array matrix of flows between facilities C : np.array matrix pf fixed costs of assigning facilities to locations Formulates a quadratic programming model from three inputs. The inputs are composed of: a matrix which describes the unit cost of moving a single asset between locations. This matrix can describe asynchronous costs that differ by direction of flow; a matrix which describes the quantity of flow between facilities. This matrix describes the quantity in the direction of flow; a matrix which desribes the fixed cost of assigning a facility to a location. Using these flows and costs, an optimization problem is formulated to determine a solution which minimizes the total cost for positioning facilities at locations. The facilities do not have to be buildings or campuses and the locations do not have to be geographical locations. See Beckmann and and Koopmans (1957) for the original reference. >>> A = np.array([[0, 5, 8, 0, 1], ... [0, 0, 0, 10, 15], ... [0, 0, 0, 13, 18], ... [0, 0, 0, 0, 0.], ... [0, 0, 0, 1, 0.]]) >>> B = np.array([[0, 8.54, 6.4, 10, 8.94], ... [8.54, 0, 4.47, 5.39, 6.49], ... [6.4, 4.47, 0, 3.61, 3.0], ... [10, 5.39, 3.61, 0, 2.0], ... [8.94, 6.49, 3.0, 2.0, 0.]]) >>> C = np.array([[2, 3, 6, 3, 7], ... [3, 9, 2, 5, 9], ... [2, 6, 4, 1, 2], ... [7, 5, 8, 5, 7], ... [1, 9, 2, 9, 2.]]) >>> model = QAPModel(A, B, C) >>> model.penalty_multiplier = 105.625 >>> Q = model.qubo.Q >>> np.sum(Q) 24318.03 """ def __init__(self, A : np.ndarray, B : np.ndarray, C: np.ndarray): self.A = A self.B = B self.C = C # N is the number of facilities (same as locations) # n is the number of variables (N ** 2) self.N = N = A.shape[0] self.upper_bound = np.ones((N**2,), dtype=np.int64) # objective A = self.A B = self.B C = self.C n = self.N ** 2 objective = np.kron(A, B) + np.diag(C.reshape((n, ))) objective += objective.T objective /= 2. self.quad_objective = objective self.linear_objective = np.zeros((n,)) # G m = 2 * self.N G = np.zeros((m, n), dtype=np.float32) for i in range(self.N): G[i, i::self.N] = 1 G[self.N + i, i*self.N:(i+1)*self.N] = 1 h = np.ones((m,)) self.lhs = G self.rhs = h