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

M.M. Drugan

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)
11 Downloads (Pure)

Samenvatting

-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.
Originele taal-2Engels
Titel2013 IEEE Congress on Evolutionary Computation (CEC), 20-23 June 2013, Cancun, Mexico
Plaats van productiePiscataway
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's2086-2093
ISBN van geprinte versie978-1-4799-0453-2
DOI's
StatusGepubliceerd - 2013
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'Instance generator for the quadratic assignment problem with additively decomposable cost function'. Samen vormen ze een unieke vingerafdruk.

Citeer dit