A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem

Year 2018, Volume: 4 Issue: 2, 124 - 128, 27.06.2018

Erdener Özçetin , Gürkan Öztürk

Abstract

In this study, quadratic assignment
problem, which is a hard combinatorial optimization problem, is examined to
solve by a new approach. To reach the optimal results by using mathematical
programming approaches cannot be possible even for some sorts of small and
middle scaled problems in a reasonable time interval. Huge amounts of data are
being progressed simultaneously by graphics processing units located on
computers’ graphics card. Therefore, a parallel iterated local search algorithm
has been proposed to solve the quadratic assignment problem by using graphics
processing units’ simultaneously progressing property. This parallel algorithm
and the sequential one on central processing units are tested and compared for test
problems in literature. Indeed, it is observed that the parallel algorithm
works averagely 6.31 times faster for Skorin problems and 11.93 times faster for
Taillard problems faster than sequentially one.

Keywords

Quadratic assignment problem (QAP), local search algorithms, graphics processing units (GPU), CUDA

References

• T. C. Koopmans ve M. J. Beckmann, “Assignment problems and the location of economic activities,” Econometrica, vol. 25, pp. 53-76, 1957.
• S. Sahni ve T. Gonzalez, “P-complete approximation problems,” Journal of the Association of Computing Machinery, vol. 23, pp. 555-565, 1976.
• S. Kirkpatrick, C. Gelat ve M. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.
• 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.
• M. Wilhelm ve T. Ward, “Solving quadratic assignment problems by 'simulated annealing',” IIE Transactions, vol. 19, pp. 107-119, 1987.
• 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.
• T. Stützle ve M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” New Ideas in Optimization,McGraw-Hill, 1999.
• 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.
• 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.
• Z. Drezner, “A New Genetic Algorithm for the Quadratic Assignment Problem,” Informs Journal on Computing, vol. 15, pp. 320-330, 2003.
• F. Glover, “Tabu Search - Part I,” ORSA Journal on Computing, vol. 1, pp. 190-206, 1989.
• J. Skorin-Kapov, “Tabu Search Applied to the Quadratic Assignment Problem,” ORSA Journal on Computing, vol. 2, pp. 33-45, 1990.
• E. D. Taillard, “Robust taboo search for the quadratic assignment problem,” Parallel Computing, vol. 17, pp. 443-455, 1991.
• A. Misevičius ve A. Ostreika, “Defining Tabu tenure for the Quadratic Assignment Problem,” Information Technology and Control, vol. 36, 2007.
• "Developer Centers: CUDA Zone,” nVIDIA,. Available: http://developer.nvidia.com/cuda/what-cuda.
• S. Tsutsui ve N. Fujimoto, “Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: A Case Study,” GECCO, Montreal, 2009.
• S. Tsutsui ve N. Fujimoto, “Fast QAP Solving by ACO with 2-opt Local Search on a GPU,” IEEE Section Congres, San Francisco, 2011.
• 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.
• 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.