PhD thesis: Solving Large-Scale Quadratic Assignment Problems

I notice that people are expecting to find my thesis here, so here goes. It was written in 2000 and while it’s always anguishing to look at things you did a long time ago, I am proud of the result. The “nug30” QAP was one of the most difficult optimization problems ever solved at the time, and it probably still ranks pretty high on the list 12 years later.

My thesis is available here.

Abstract:

The quadratic assignment problem (QAP) is the problem of finding an assignment of an equal number of facilities to locations that minimizes the transportation cost between facilities. The large number of possible assignments along with the interdependence of the cost on the flows and distances causes QAP to be an extremely difficult problem to solve in practice.

Branch-and-bound algorithms are typically used to find exact solutions to QAP. A branch-and-bound algorithm solves a QAP by assigning some facilities to locations, and computing lower bounds on these smaller subproblems. The use of lower bounds allows the algorithm to eliminate from consideration partial assignments that cannot lead to a solution, and via this process of elimination efficiently determine an optimal assignment.

This dissertation proposes a new branch-and-bound implementation capable of solving previously unsolved quadratic assignment problems. The first ingredient is a new continuous relaxation of QAP based on convex quadratic programming, resulting in an efficiently computed, effective lower bounding procedure. The new bound is a key component in an improved branch-and-bound algorithm that uses information provided by the continuous relaxation to intelligently extend the search for optimal solutions.

Even though the performance of our branch-and-bound algorithm surpasses previous implementations on a range of standard test problems, large computational resources are required. The solution of QAPs as small as thirty facilities and locations requires years of sequential computation. Grid computing resources allow hundreds of workstations to work on the solution of a QAP at once. The MW grid computing tool was used to produce an efficient, fault-tolerant parallel branch-and-bound implementation. This implementation was used to solve the Nugent 30 QAP, unsolved since 1968, over a period of seven days using 1000 machines.

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