Example $4$: Quadratic Assignment Problem $($Week $10)$

An engineer needs to locate five machines $($Mach$.$A$-$Mach.E$)$ to five locations $($Loc$\mathrm{.}1-$Loc$\mathrm{.}5)$ in the

assembly department. The material flows between machines and the distances between locations are

given in the below tables. The material handling cost is given by ${\displaystyle \underset{ij}{\overset{?}{}}}{f}_{ij}**d_{ij}$ where $f_{ij}$ and $d_{ij}$ are the

flow and distance between machine pair i and $j.$ This problem can easily be modeled as a quadratic

assignment problem $($QAP$).$

a$)$ Using ordering method, determine a lower bound for the material handling cost.

b$)$ Assume that pairwise exchange method finds a solution with a cost of $140.$ What is the optimality

gap?