QAPLIB - A Quadratic Assignment Problem Library

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


Surveys and Dissertations Concerning QAP since 1990


Surveys

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

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 still a broad interest in this difficult combinatorial optimization problem. Eventhough there has not been substantial improvement regarding the solvability of larger problem instances, these dissertations contain many ideas which are certainly 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.

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.

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
March 2000. Eranda Çela, cela@opt,math.tu-graz.ac.at