An algorithm for construction of test cases for the quadratic assignment problem

An algorithm for construction of test cases for the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20011951
Country: Lithuania
Volume: 11
Issue: 3
Start Page Number: 281
End Page Number: 296
Publication Date: Jul 2000
Journal: Informatica
Authors:
Keywords: quadratic assignment
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.

Reviews

Required fields are marked *. Your email address will not be published.