QAPLIB - A Quadratic Assignment Problem Library

R.E. BURKARD, E. ÇELA, S.E. KARISCH and F. RENDL


Surveys and Dissertations Concerning QAP


Surveys

The following list of books and surveys is given in reverse order of their appearance.

E.M. LOIOLA, N.M.M. DE ABREU, P.O. BOAVENTURA-NETTO, P.M. HAHN, AND T. QUERIDO, A survey for the quadratic assingment problem [LoAbBoHaQu:06], 2006.

R.E. BURKARD, E. ÇELA, P.M. PARDALOS and L. PITSOULIS, The quadratic assignment problem [BCPP:98], 1998.

E.ÇELA. The Quadratic Assignment Problem: Theory and Algorithms [Cela:98], 1998.

R.E. BURKARD and E. ÇELA. Quadratic and three-dimensional assignment problems. [BuCe:96], 1996.

P.M. PARDALOS, F. RENDL, and H. WOLKOWICZ. The quadratic assignment problem: a survey of recent developments [PaReWo:94], 1994.

P.M. PARDALOS and H. WOLKOWICZ, editors. Quadratic assignment and related problems [PaWo:94], 1994.

R.E. BURKARD. Locations with spatial interactions: the quadratic assignment problem [Burkard:91], 1991.


Dissertations

The following list of dissertations considering the quadratic assignment problem shows that there is broad interest in this difficult combinatorial optimization problem. These dissertations contain many ideas which are a strong foundation for successful future work on QAP.

A. Bouras [Bouras:96] considered special cases of QAP where the coefficient matrices have a low rank, especially rank one. He also proposes a heuristic based on matrix approximations by matrices with low rank.

N. Brixius [Brixius:00] proposed a lower bounding technique for QAP based on convex quadratic programming. This bound was used in a new branch-and-bound implementation running on a grid computing platform that was able to solve previously unsolved QAPs.

A. Bruengger [Bruengger:97] covers a significant amount of work regarding the QAP. One chapter compares various heuristics, and one chapter covers a method used by [BrClMaPe:96] to solve several previously unsolved instances.

E. Cela [Cela:95] investigated the computational complexity of specially structured quadratic assignment problems. Moreover, she considered a generalization of QAP, the so called biquadratic assignment problem.

P.M. Hahn [Hahn:68] developed a cutting plane technique for solving the QAP, based upon the resolvent sequence. He also introduced a new lower bound based on the Hungarian method that is still among the best available for exact solution of medium-to-large QAP instances.

T.A. Johnson [Johnson:92] introduced new solution procedures based on linear programming. The linear formulation derived in her thesis theoretically dominates alternate linear formulations for QAP.

V. Kaibel [Kaibel:97] investigated the the QAP polytope and derived the first large class of facet defining inequalities for these polytopes, the box inequalities. Tight bounds or even optimal solutions can be computed using these in a cutting plane approach.

S.E. Karisch [Karisch:95] presented nonlinear approaches for QAP. These provide the currently strongest lower bounds for problems instances whose distance matrix contains distances of a rectangular grid and for smaller sized general problems.

Y. Li [Li:92] introduced beside other ideas lower bounding techniques based on reductions, GRASP and a problem generator for QAP.

F. Malucelli [Malucelli:93] proposed a lower bounding technique for QAP based on a reformulation scheme and implemented it in a branch and bound code. Some new applications of QAP in the field of transportation were also presented.

T. Mautor [Mautor:92] focusses on parallel implementations and exploits the metric structure of the Nugent instances to reduce the branching tree considerably.

M. Rijal [Rijal:95] investigated structural properties of the QAP polytope. The starting point is the quadric Boolean polytope.

Q. Zhao [Zhao:96] investigated semidefinite programming approaches for the QAP. Tight relaxations and bounds are obtained by exploiting the geometrical structure of the convex hull of permutation matrices.



GO BACK TO MAIN PAGE OF QAPLIB
Jan 2007. Peter Hahn, hahn@seas.upenn.edu