Instance generator for the quadratic assignment problem with additively decomposable cost function

M.M. Drugan

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
11 Downloads (Pure)

Abstract

-Quadratic assignment problems (QAPs) are NP-hard combinatorial optimization problems often used to compare the performance of meta-heuristics. In this paper, we propose a QAP problem instance generator whose instances can be used as benchmark for meta-heuristics. Our generator aggregates various QAP instances into a larger size QAP instance in order to obtain an large size, additively decomposable QAP. We assume that a QAP instance that is difficult for local search has many local optima from which local search needs to escape from. We call the resulting QAPs the composite QAP instances (cQAPs). We use numerical and empirical techniques for the landscape analysis of generated composite QAPs. The comparison between our QAP instances with the other QAPs from the literature classify cQAPs as difficult. We show that heuristic algorithms that exploit the particularities of the cQAP search space, like iterated local search, can outperform other heuristics that do not consider the structure of this search space, like the multi-restart local search.
Original languageEnglish
Title of host publication2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages2086-2093
ISBN (Print)978-1-4799-0453-2
DOIs
Publication statusPublished - 2013
Externally publishedYes

Cite this