VERY LARGE-SCALE NEIGHBORHOOD SEARCH FOR THE QUADRATIC ASSIGNMENT PROBLEM

Ravindra Ahuja, Krishna Jha, James Orlin and Dushyant Sharma

No 4386-02, Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management

Abstract: The Quadratic Assignment Problem (QAP) consists of assigning n facilities to n locations so as to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse settings, is known to be NP-hard, and can be solved to optimality only for fairly small size instances (typically, n Â‰Ä 25). Neighborhood search algorithms are the most popular heuristic algorithms to solve larger size instances of the QAP. The most extensively used neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities and thus has size O(n2). Previous efforts to explore larger size neighborhoods (such as 3-exchange or 4-exchange neighborhoods) were not very successful, as it took too long to evaluate the larger set of neighbors. In this paper, we propose very largescale neighborhood (VLSN) search algorithms where the size of the neighborhood is very large and we propose a novel search procedure to heuristically enumerate good neighbors. Our search procedure relies on the concept of improvement graph which allows us to evaluate neighbors much faster than the existing methods. We present extensive computational results of our algorithms on standard benchmark instances. These investigations reveal that very large-scale neighborhood search algorithms give consistently better solutions compared the popular 2- exchange neighborhood algorithms considering both the solution time and solution accuracy.

Keywords: Quadratic Assignment Problem (QAP) (search for similar items in EconPapers)
Date: 2003-01-27
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/1721.1/1801 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mit:sloanp:1801

Ordering information: This working paper can be ordered from
MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA

Access Statistics for this paper

More papers in Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA. Contact information at EDIRC.
Bibliographic data for series maintained by None ( this e-mail address is bad, please contact ).