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

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