ANALYSIS AND PERFORMANCE MEASUREMENT OF EXISTING SOLUTION METHODS OF QUADRATIC ASSIGNMENT PROBLEM

Year 2013, Volume: 3 Issue: 2, 557 - 570, 01.12.2013

Morteza Karamı Sadegh Nıroomand Nima Mırzaeı Bela Vızvarı

Abstract

Quadratic Assignment Problem (QAP) is known as one of the most difficult combinatorial optimization problems that
is classified in the category of NP-hard problems. Quadratic Assignment Problem Library (QAPLIB) is a full database of QAPs
which contains several problems from different authors and different sizes. Many exact and meta-heuristic solution methods have
been introduced to solve QAP. In this study we focus on previously introduced solution methods of QAP e.g. Branch and Bound
(B&B), Simulated Annealing (SA) Algorithm, Greedy Randomized Adaptive Search Procedure (GRASP) for dense and sparse QAPs.
The codes of FORTRAN for these methods were downloaded from QAPLIB. All problems of QAPLIB were solved by the above- mentioned methods. Several results were obtained from the computational experiments part. The Results show that the Branch and
Bound method is able to introduce a feasible solution for all problems while Simulated Annealing Algorithm and GRASP methods are not able to find any solution for some problems. On the other hand, Simulated Annealing and GRASP methods have shorter run
time comparing to the Branch and Bound method. In addition, the performance of the methods on the objective function value is
discussed.

Keywords

Quadratic Assignment Problem, Quadratic Assignment Problem Library, Branch and Bound, Simulated Annealing, Greedy Randomized Adaptive Search Procedure