An Algorithm for Construction of Test Cases for the Quadratic Assignment Problem

Article type: Research Article

Authors: Palubeckis, Gintaras

Affiliations: Department of Practical Informatics, Kaunas University of Technology, Studentų 50, 3031 Kaunas, Lithuania. E-mail: gintaras@soften.ktu.lt

Abstract: In this paper we present an algorithm for generating quadratic assignment problem (QAP) instances with known provably optimal solution. The flow matrix of such instances is constructed from the matrices corresponding to special graphs whose size may reach the dimension of the problem. In this respect, the algorithm generalizes some existing algorithms based on the iterative selection of triangles only. The set of instances which can be produced by the algorithm is NP-hard. Using multi-start descent heuristic for the QAP, we compare experimentally such test cases against those created by several existing generators and against Nugent-type problems from the QAPLIB as well.

Keywords: combinatorial optimization, quadratic assignment problem, test cases

DOI: 10.3233/INF-2000-11306

Journal: Informatica, vol. 11, no. 3, pp. 281-296, 2000