To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
Given a set and matrices = ( ) and = ( ), the quadratic assignment problem (QAP) can be stated as follows:
where is the set of all permutations of . One of the major applications of the QAP is in location theory where the matrix is the flow matrix, i.e. is the flow of materials from facility~ to facility~ , and is the distance matrix, i.e. represents the distance from location~ to location~ . The cost of simultaneously assigning facility~ to location~ and facility~ to location~ is . The objective is to find an assignment of all facilities to all locations (i.e. a permutation ), such that the total cost of the assignment is minimized. With an appropriate choice of the flow matrix, the traveling salesman problem is a special class of QAP. Other applications include scheduling, manufacturing, the backboard wiring problem in electronics, parallel and distributed computing, and statistical data analysis. The term ``quadratic" comes from the reformulation of the problem as an optimization problem with a quadratic objective function.
From the computational complexity point of view the QAP is one of the most difficult problems to solve, as it is in the class of -hard problems. Currently, solving general problems of size is still considered intractable. This problem continues to be very interesting and stimulating both from computational and theoretical points of view.
On May 20--21, 1993, a workshop on ``Quadratic Assignment and Related Problems'', hosted by the Center for Discrete Mathematics and Theoretical Computer Science (organized by P. M. Pardalos and H. Wolkowicz), was held at Rutgers University. Participants from different countries gave the meeting an international component. The workshop was a success because it fostered many interactions between researchers from academia and industry. The editors also hope that this volume will lead to continuing developments in the important area of nonlinear assignment problems.
The workshop on QAP focussed on recent computational approaches and applications. About twenty invited speakers presented results on new techniques and applications. The techniques included eigenvalue estimates and reduction techniques for lower bounds, parallelization, genetic algorithms, polyhedral approaches, greedy, and adaptive search algorithms. The applications included graph bandwidth problems, telecommunications network design, load balancing, VLSI design, data association problems, and multidimensional assignment problems. This volume comprises a collection of research papers invited for presentation at the workshop.
We are indebted to DIMACS for their help in organizing the workshop and in arranging the publication of the proceedings. We would also like to take this opportunity to thank the participants of the workshop, the authors, the anonymous referees, and the American Mathematical Society for helping us produce this volume.
Foreward ix Preface xi The Quadratic Assignment Problem: A Survey and Recent Developments 1 Panos M. Pardalos, Franz Rendl, and Henry Wolkowicz Improved Linear Programming-based Lower Bounds for the Quadratic Assignment Proglem 43 Warren P. Adams and Terri A. Johnson Advanced Search Techniques for Circuit Partitioning 77 Shawki Areibi and Anthony Vannelli A Genetic Algorithm for a Special Class of the Quadratic Assignment Problem 99 Thang Nguyen Bui and Byung Ro Moon On the Biquadratic Assignment Problem 117 Rainer E. Burkard, Eranda Cela, and Bettina Klinz A Reformulation Scheme and New Lower Bounds for the QAP 147 Paolo Carraresi and Federico Malucelli A Constructive Method to Improve Lower Bounds for the Quadratic Assignment Problem 161 Jaishankar Chakrapani and Jadranka Skorin-Kapov Genetic Hybrids for the Quadratic Assignment Problem 173 Charles Fleurent and Jacques A. Ferland Domination & Separation Applied to the Quadratic Assignment Proglem 189 Scott W. Hadley Trust Regions and Relaxations for the Quadratic Assignment Problem 199 Stefan E. Karisch, Franz Rendl, and Henry Wolkowicz Stochastic Quadratic Assignment Problems 221 Wu-Ji Li and J. MacGregor Smith A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem 237 Yong Li, Panos M. Pardalos, and Mauricio G.C. Resende Difficulties of Exact Methods for Solving the Quadratic Assignment Problem 263 Thierry Mautor and Catherine Roucairol Using QAP Bounds for the Circulant TSP to Design Reconfigurable 275 Elena Medova Approximation of Association Data by Structures and Clusters 293 Boris Mirkin Partitioning Multiple Data Sets: Multidimensional Assignments and Lagrangian Relaxation 317 Aubrey B. Poore and Nenad Rijavec A Quadratic Partial Assignment and Packing Model and Algorithm for the Airline Gate Assignment Problem 343 Hanif D. Sherali and Eric L. Brown
Index of Volumes
DIMACS Homepage