Quadratic Assignment Problems, Part I

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.

Author: natebrix

Follow me on twitter at @natebrix.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s