TY  - JOUR
T1  - A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem
AU  - Özçetin, Erdener
AU  - Öztürk, Gürkan
PY  - 2018
DA  - June
Y2  - 2018
JF  - International Journal of Engineering Technologies IJET
JO  - IJET
PB  - İstanbul Gelisim University
WT  - DergiPark
SN  - 2149-0104
SP  - 124
EP  - 128
VL  - 4
IS  - 2
LA  - en
AB  - In this study, quadratic assignmentproblem, which is a hard combinatorial optimization problem, is examined tosolve by a new approach. To reach the optimal results by using mathematicalprogramming approaches cannot be possible even for some sorts of small andmiddle scaled problems in a reasonable time interval. Huge amounts of data arebeing progressed simultaneously by graphics processing units located oncomputers’ graphics card. Therefore, a parallel iterated local search algorithmhas been proposed to solve the quadratic assignment problem by using graphicsprocessing units’ simultaneously progressing property. This parallel algorithmand the sequential one on central processing units are tested and compared for testproblems in literature. Indeed, it is observed that the parallel algorithmworks averagely 6.31 times faster for Skorin problems and 11.93 times faster forTaillard problems faster than sequentially one.
KW  - Quadratic assignment problem (QAP)
KW  - local search algorithms
KW  - graphics processing units (GPU)
KW  - CUDA
CR  - T. C. Koopmans ve M. J. Beckmann, “Assignment problems and the location of economic activities,” Econometrica, vol. 25, pp. 53-76, 1957.
CR  - S. Sahni ve T. Gonzalez, “P-complete approximation problems,” Journal of the Association of Computing Machinery, vol. 23, pp. 555-565, 1976.
CR  - S. Kirkpatrick, C. Gelat ve M. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.
CR  - R. Burkard ve F. Rendl, “A thermodynamically motivated simulation procedure for combinatorial optimization problems,” European Journal of Operational Research, vol. 17, pp. 169-174, 1984.
CR  - M. Wilhelm ve T. Ward, “Solving quadratic assignment problems by 'simulated annealing',” IIE Transactions, vol. 19, pp. 107-119, 1987.
CR  - N. Abreu, T. Querido ve P. Boaventura-Netto, “A simulated annealing for the quadratic assignment problem,” Rairo-Operations Research, vol. 33, pp. 249-273, 1999.
CR  - T. Stützle ve M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” New Ideas in Optimization,McGraw-Hill, 1999.
CR  - M. Dorigo, V. Maniezzo ve A. Colorni, “The Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, vol. 26, pp. 1-13, 1996.
CR  - J. Kochhar, B. Foster ve S. Heragu, “A genetic algorithm for the unequal area facility layout problem,” Computers & Operations Research, vol. 25, pp. 583-594, 1998.
CR  - Z. Drezner, “A New Genetic Algorithm for the Quadratic Assignment Problem,” Informs Journal on Computing, vol. 15, pp. 320-330, 2003.
CR  - F. Glover, “Tabu Search - Part I,” ORSA Journal on Computing, vol. 1, pp. 190-206, 1989.
CR  - J. Skorin-Kapov, “Tabu Search Applied to the Quadratic Assignment Problem,” ORSA Journal on Computing, vol. 2, pp. 33-45, 1990.
CR  - E. D. Taillard, “Robust taboo search for the quadratic assignment problem,” Parallel Computing, vol. 17, pp. 443-455, 1991.
CR  - A. Misevičius ve A. Ostreika, “Defining Tabu tenure for the Quadratic Assignment Problem,” Information Technology and Control, vol. 36, 2007.
CR  - "Developer Centers: CUDA Zone,” nVIDIA,. Available: http://developer.nvidia.com/cuda/what-cuda.
CR  - S. Tsutsui ve N. Fujimoto, “Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: A Case Study,” GECCO, Montreal, 2009.
CR  - S. Tsutsui ve N. Fujimoto, “Fast QAP Solving by ACO with 2-opt Local Search on a GPU,” IEEE Section Congres, San Francisco, 2011.
CR  - M. Czapinski, “An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem CUDA platform,” J. Parallel Distrib. Comput., vol. 73(11), pp. 1461-1468, 2013.
CR  - E. Özçetin ve G. Öztürk, “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units,” ANADOLU UNIVERSITY JOURNAL OF SCIENCE AND TECHNOLOGY –A Applied Sciences and Engineering, vol. 17, no. 1, pp. 167-180, 2016.
UR  - https://dergipark.org.tr/en/pub/ijet/issue//346573
L1  - https://dergipark.org.tr/en/download/article-file/510500
ER  -