Generating QAP instances with known optimum solution and additively decomposable cost function

M.M. Drugan

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
202 Downloads (Pure)

Abstract

Quadratic assignment problems (QAPs) is a NP-hard combinatorial optimization problem. QAPs are often used to compare the performance of meta-heuristics. In this paper, we propose a QAP problem instance generator that can be used for benchmarking for heuristic algorithms. Our QAP generator combines small size QAPs with known optimum solution into a larger size QAP instance. We call these instances composite QAPs (cQAPs), and we show that the cost function of cQAPs is additively decomposable. We give mild conditions for which a cQAP instance has known optimum solution. We generate cQAP instances using uniform distributions with different bounds for the component QAPs and for the rest of the cQAP elements. Numerical and analytical techniques that measure the difficulty of the cQAP instances in comparison with other QAPs from the literature are introduced. These methods point out that some cQAP instances are difficult for local search with many local optimum of various values, low epistasis and non-trivial asymptotic behaviour.
Original languageEnglish
Pages (from-to)1138-1172
JournalJournal of Combinatorial Optimization
Volume30
Issue number4
DOIs
Publication statusPublished - 2015

Fingerprint

Dive into the research topics of 'Generating QAP instances with known optimum solution and additively decomposable cost function'. Together they form a unique fingerprint.

Cite this