Solving Small QAPs

Psychologically it is, of course, disadvantageous to start the last chapter with a disclaimer, but this is exactly what we are going to do. The software system that we are going to describe here is of a preliminary nature and our computational results should by no means be interpreted as limiting the potential of branch-and-cut algorithms for the solution of quadratic assignment and related quadratic zero-one optimization problems. The software system came about from our desire to write an interesting introductory chapter for this monograph dealing with the fascinating world of location, scheduling and design problems -see Chapters 1.3, 1.4 and 1.5. As an afterthought came then the idea to test the software system on a somewhat larger sample of the problems from QAPLIB. In spite of our reservations we have included this material in the book because it seems to fill a gap in the literature on how to solve quadratic assignment problems. Our efforts in locating suitable references notwithstanding and despite the fact that every author that we have read on quadratic assignment calls the problem a (mixed) zero-one programming problem, nobody seems to have taken the pain to solve QAPs via a standard mixed integer programming code using ordinary branch-and-bound. The development effort that is necessary to actually write such a software system for QAP is minimal — it took one of the authors about seven days of intense programming work to “string it all together and get the job done.”