Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods

Zvi Drezner (), Peter Hahn () and Éeric Taillard ()

Annals of Operations Research, 2005, vol. 139, issue 1, 65-94

Abstract: This paper reports heuristic and exact solution advances for the Quadratic Assignment Problem (QAP).QAPinstances most often discussed in the literature are relatively well solved by heuristic approaches. Indeed, solutions at a fraction of one percent from the best known solution values are rapidly found by most heuristic methods. Exact methods are not able to prove optimality for these instances as soon as the problem size approaches 30 to 40. This article presents new QAP instances that are ill conditioned for many metaheuristic-based methods. However, these new instances are shown to be solved relatively well by some exact methods, since problem instances up to a size of 75 have been exactly solved. Copyright Springer Science + Business Media, Inc. 2005

Keywords: quadratic assignment problem; local search; branch & bound; benchmarks (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-005-3444-z (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:139:y:2005:i:1:p:65-94:10.1007/s10479-005-3444-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-005-3444-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().