In a previous series I talked a bit about linear assignment problems (LAPs) and provided code for a simple LAP solver. Now I want to spend a few posts on LAP’s big brother, the Quadratic Assignment Problem. In an LAP we are trying to assign objects in one set to an equal number of objects in another set, where we are given the cost of assigning any pair of objects. In QAP we still have two sets of objects – and I will stick with the original formulation of the problem (from the 50′s) and call the first step of objects “facilities” and the second set “locations”. Imagine that we are going to build a bunch of computer labs in different rooms of a building, for example. Suppose that each lab has a different purpose, and the rooms are wired up and we’re trying to figure out where to put each lab. The quadratic assignment problem is the problem of finding an assignment
of an equal number of facilities to locations that minimizes the transportation cost between facilities. In my example, the transportation cost is a product of how far the rooms are from each other and how often one travels from one lab to the other.
QAPs are interesting problems in part because they are so difficult to solve. Finding the optimal assignment is an NP-hard problem. In upcoming posts I will write down the problem more formally, and explore some heuristics for QAP, as well as some tools for finding exact solutions for QAP.