Try the QAP java Applet !
In a standard problem in location theory, we are given a set of n locations and n facilities, and told to assign each facility to a location. To measure the cost of each possible assignment---there are n! of them!---we multiply the prescribed flow between each pair of facilities by the distance between their assigned locations, and sum over all the pairs. Our aim is to find the assignment that minimizes this cost, and this problem is precisely a quadratic assignment problem.
The links here take you to a java applet that will let you test your skill at finding good solutions to quadratic assignment problems. You can input the assigment of the facilities to the locations at the top of the applet, and the cost of the assignment will be computed for you. The required flows between facilities are listed to the right of the applet. If it is all very confusing, it might be best to go through The Facility Location Example.
You will find (or have found) that as the problems get larger, it becomes much, much more difficult to find the optimal solution. As n grows large it becomes impossible to enumerate all the possible assignments, even by fast computers. For example, if n=25 and a computer were able to evaluate 10 billion assignments per second, it would still take nearly 50 million years to evaluate all assignments!!!
Instead, advanced mathematical techniques, usually based on the idea of Branch and Bound are used to solve problems of this size.
Give us your comments.
[ OTC Home Page | NEOS Server | NEOS Guide | Case Studies ]