The Quadratic Assignment Problem:
An Example of Combinatorial Optimization
The picture above shows one possible solution to a quadratic assignment problem/facility location problem with four facilities.
The permutation p corresponding to this
graphical solution is ( 2, 1, 4, 3 ). This means that :
- facility 2
has been assigned to location 1,
- facility 1 assigned to
location 2,
- facility 4 assigned to location 3,
- facility 3 assigned to
location 4.
The
lines drawn between the facilities implies that there is a
required flow between the facilities, and the thickness of the
line denotes the value of the required flow.
The goal, in some sense, is to try to get the "fat" lines as close
together as possible.
To make the idea more concrete, let's say that the
distances are
- d(1,2) = 22,
- d(1,3) = 53,
- d(2,3) = 40,
- d(3,4) = 55.
Also, the required flows between facilities are
- f(2,4) = 1,
- f(1,4) = 2,
- f(1,2) = 3,
- f(3,4) = 4.
The assignment cost of the permutation shown is
d(1,2) * f(1,2) + d(1,3) * f(2,4) + d(2,3) * f(1,4) + d(3,4) * f(3,4)
=
22 * 3 + 53 * 1 + 40 * 2 + 55 * 4 = 419.
This is not the best possible permutation. Can you determine the
correct
answer?
To try your luck, see the applet of size 4.
Comments and Suggestions
Give us your comments.
Acknowledgments
[ OTC Home Page | NEOS Server | NEOS Guide | Case
Studies ]