DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME SIXTEEN
TITLE: "Quadratic Assignment and Related Problems"
EDITORS: Panos M. Pardalos and Henry Wolkowicz
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.



PREFACE


In the last decade we have seen a dramatic increase in the size of NP-hard combinatorial optimization problems that can be solved in practice. This is due to advances in data structures, new algorithmic developments and major advances in computer hardware. It is not unusual today to solve large-scale combinatorial problems, such as maximum clique problems on graphs with thousands of vertices and millions of edges, or traveling salesman problems with several thousands of cities. There is an exception in the class of combinatorial optimization problems, the quadratic assignment problem (QAP), which is still considered to be of large-scale when , where is the problem dimension.

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.


TABLE OF CONTENTS





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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.