zbMATH — the first resource for mathematics

New benchmark instances for the QAP and the experimental analysis of algorithms. (English) Zbl 1177.90424
Gottlieb, Jens (ed.) et al., Evolutionary computation in combinatorial optimization. 4th European conference, EvoCOP 2004, Coimbra, Portugal, April 5–7, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21367-8/pbk). Lecture Notes in Computer Science 3004, 199-209 (2004).
Summary: The quadratic assignment problem arises in a variety of practical settings. It is known to be among the hardest combinatorial problems for exact algorithms. Therefore, a large number of heuristic approaches have been proposed for its solution. In this article we introduce a new, large set of QAP instances that is intended to allow the systematic study of the performance of metaheuristics in dependence of QAP instance characteristics. Additionally, we give computational results with several high performing algorithms known from literature and give exemplary results on the influence of instance characteristics on the performance of these algorithms.
For the entire collection see [Zbl 1051.68010].

90C59 Approximation methods and heuristics in mathematical programming
90C10 Integer programming
90C20 Quadratic programming
Full Text: DOI