Project # 4

Assignment

The goal of the project is the implementation of a solution to the Quadratic Assignment Problem (QAP).

Problem descrption. QAP consists in finding the optimal assignment of a set of equipment/factories (facilities) to a set of locations (locations) with respect to the distances and flows of goods between them. The solution to the problem is to assign devices to a location that minimizes the total cost of interconnection, taking into account both distances and flows. Informally, we can think of it, for example, as our goal will be to find the location of the factories so that the factories between which there is a lot of traffic are close to each other.

However, QAP has more possible applications and can be used, for example, in the design of printed circuit boards. A particular instance of the problem is defined using a distance matrix (D), a flow matrix (F), and a set of constraints ensuring that each device is assigned to exactly one location and each location is assigned to exactly one device. When this condition is met, the solution to the problem is a permutation.

Fig 1: QAP example

Mathematically, a simple version of QAP can be formulated as follows: let us have a set of \(n\) devices (factories) and \(n\) locations. The distance between locations is defined by a matrix \(D = \{d_{ij}\} \in \mathbb{R}^{n\times n}\) and the intensity of the flows between the factories by the matrix \(F = \{f_{ij}\} \in \mathbb{R}^{n\times n}\). TWe can imagine this as the amount of goods that travel between \(i\) and \(j\).

The goal of the QAP solution is to find the assignment of devices to locations. Here, with the same number of devices and places, we can imagine it as a permutation of device, \(\pi = (\pi_1, \pi_2,\ldots \pi_n)\), which will minimize the following cost function: \[\min_{\pi\in\mathcal{S}_n} f_{\mathrm{QAP}}(\pi),\] \[f_{\mathrm{QAP}}(\pi) = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} D_{ij} \cdot F_{\pi(i)\pi(j)},\] wherw \(\mathcal{S}_n\) is the set of all permutations of the length \(n\).

Assignment. Implement a QAP solution (for problem instance tai12a.dat) using the brute-force and Branch and Bound (e.g., backtracking) with the sharing of the best-found solution.

References

  1. Çela, E. 1998. The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht.