2. Quadratic Assignment Problem (QAP)¶
In the linear assignment problem (LAP) we looked at in Net Mod 1, the cost of making an assignment of i to k did not depend on any other j being assigned a different l; in the quadratic assignment problem (QAP), the cost of making an assignment of i to k depends on the assignment of all other j's to particular l's. The QAP can be formulated as the following binary integer program (BIP):
$ \begin{eqnarray*} \quad \textbf{QAP:} \quad \mbox{Minimize} \quad \sum_{i \in N} \sum_{j \in N} \sum_{k \in N} \sum_{l \in N} c_{ijkl} x_{ik} x_{jl} \\ \quad \mbox{subject to} \quad \sum_{i \in N} x_{ik} &=& 1 \mbox{,} &\quad k \in N \\ \sum_{k \in N} x_{ik} &=& 1 \mbox{,} &\quad i \in N \\ x_{ik} &\in& \bigl\{ 0, 1 \bigr\}, \end{eqnarray*} $
where
$ \begin{eqnarray*} \quad x_{ik} &=& \begin{cases} 1, & \mbox{if } i \mbox{ is assigned to } k \\ 0, & \mbox{otherwise} \end{cases} \\ c_{ijkl} &=& \mbox{cost of assigning } i \mbox{ to } k \mbox{ if } j \mbox{ is assigned to } l. \end{eqnarray*} $
The objective function is quadratic because of the $x_{ik} x_{jl}$ terms, and, as a result, is an example of a nonlinear programming problem.
In comparison, the following LAP formulation is a linear programming problem because of the single $x_{ij}$ term in the objecive:
$ \begin{eqnarray*} \quad \textbf{LAP:} \quad \mbox{Minimize} \quad \sum_{i \in N} \sum_{j \in N} c_{ij} x_{ij} \\ \quad \mbox{subject to} \quad \sum_{j \in N} x_{ij} &\le& 1\mbox{,} &\quad i \in N \\ \sum_{i \in N} x_{ij} &=& 1\mbox{,} &\quad j \in N \\ x_i &\ge& 0. \end{eqnarray*} $
Layout Problems¶
The QAP can be used to model layout problems, where a set of resources are assigned to a set of sites. The major cost is the cost of moving an item from site to site as different items visit different resources. The items can be parts being fabricated or patients visiting stations in a clinic. The sequence of resources needs by each item is termed its routing, and each resource can be shared between several items, making the total cost (typically, total distance) dependant on the assignment (or layout) of the resources to the sites.
In a layout problem, the QAP cost term can be separated into two terms:
$ \begin{eqnarray*} \quad c_{ijkl} &=& \mbox{cost of assigning resource } i \mbox{ to site } k \mbox{ if resource } j \mbox{ is assigned to site } l \\ &=& w_{ij} d_{kl} \end{eqnarray*} $
where
$ \begin{eqnarray*} \quad w_{ij} &=& \mbox{total flow from resource } i \mbox{ to resource } k \\ &=& \sum_{p \in P} w_{ijp} \\ w_{ijp} &=& \mbox{total flow from } i \mbox{ to } j \mbox{ for item } p \\ d_{kl} &=& \mbox{distance from site } k \mbox{ to site } l. \end{eqnarray*} $
Ex 4: 3-Item, 4-Machine Layout¶
In this example, A, B, and C are three different types of items transferred between four machine resources, as shown below. The total number of each item to be produced per shift is 24, 10, and 12, respectively, and their routings from machine to machine are:
$ \quad A: 1–2–3–4; \quad B: 2–4–1–2–3; \quad C: 3–4–1–2–4 $
There are four possbile sites at which the machines can be located. Each site is represented as a circle and its cooridinate along 1-D is given:
The site-to-site distance matrix D is:
