Analysis and performance measurement of existing solution methods of quadratic assignment problem

Abstract

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). …………………………………………………………………………………………………………………………

ÖZ: NP-zor problem kategorisinde sınıflandırılmış olan karesel Atama problemi (KAP) bilinen en zor birleşimsel optimizasyon problemidir. karesel Atama problem kütüphanesi (QAPLIB) birçok KAP veritabanı içerir ve bu veritabanlarının farklı yazar ve boyutları vardır. Birçok sezgi-ötesi çözüm yöntemleri KAP için tanımlanmıştır. Bu tezde, yoğun ve seyrek KAP için önceden tanımlanmış dört çözüm metotları olan; Dal sınır yöntemi, benzetim tavlama algoritması ve Greedy Randomized Adaptive Search Procedure (GRASP) vardır. Bu yöntemleri FORTRAN kodları KAP kütüphanesinden indirilmiştir. Bütün KAP kütüphanesindeki sorunlar bu yöntemleri çözülmüştür. Birtakım sonuçlar deneysel hesaplamalı kısımlar tarafından elde edilmiştir. Tüm problemler için Dal Sınır yöntemi, sonuçlara göre uygun bir çözümü tanıtmanın mümkün olabileceğini göstermektedir. Tavlama benzetimi algoritması ve GRASP‟ın bazı sorunlar için herhangi bir uygun çözüm bulması mümkün değildir. Buna rağmen, Tavlama Benzetimi ve GRASP Metotları, Dal Sınır yöntemine göre daha kısa bir . Anahtar Kelimeler: Karesel Atama Problemi, karesel Atama Problem Kütüphanesi, Dal Sınır Yöntemi, Tavlama Benzetim Algoritması, Greedy Randomized Adaptive Search Procedure (GRASP).