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 full database of QAPs which contains several problems from different authors and with different sizes. Many exact and meta-heuristic solution methods have been introduced to solve QAP. In this thesis we focus on four previously introduced solution method 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. The performance of the methods on the objective function value is discussed also. Keywords: Quadratic Assignment Problem, QAPLIB, Branch and Bound, Simulated Annealing, Greedy Randomized Adaptive Search Procedure (GRASP). …………………………………………………………………………………………………………………………