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

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

1. T. C. Koopmans ve M. J. Beckmann, “Assignment problems and the location of economic activities,” Econometrica, vol. 25, pp. 53-76, 1957.
2. S. Sahni ve T. Gonzalez, “P-complete approximation problems,” Journal of the Association of Computing Machinery, vol. 23, pp. 555-565, 1976.
3. S. Kirkpatrick, C. Gelat ve M. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.
4. 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.
5. M. Wilhelm ve T. Ward, “Solving quadratic assignment problems by 'simulated annealing',” IIE Transactions, vol. 19, pp. 107-119, 1987.
6. 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.
7. T. Stützle ve M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” New Ideas in Optimization,McGraw-Hill, 1999.
8. 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.

9. 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.
10. Z. Drezner, “A New Genetic Algorithm for the Quadratic Assignment Problem,” Informs Journal on Computing, vol. 15, pp. 320-330, 2003.
11. F. Glover, “Tabu Search - Part I,” ORSA Journal on Computing, vol. 1, pp. 190-206, 1989.
12. J. Skorin-Kapov, “Tabu Search Applied to the Quadratic Assignment Problem,” ORSA Journal on Computing, vol. 2, pp. 33-45, 1990.
13. E. D. Taillard, “Robust taboo search for the quadratic assignment problem,” Parallel Computing, vol. 17, pp. 443-455, 1991.
14. A. Misevičius ve A. Ostreika, “Defining Tabu tenure for the Quadratic Assignment Problem,” Information Technology and Control, vol. 36, 2007.
15. "Developer Centers: CUDA Zone,” nVIDIA,. Available: http://developer.nvidia.com/cuda/what-cuda.
16. S. Tsutsui ve N. Fujimoto, “Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: A Case Study,” GECCO, Montreal, 2009.
17. S. Tsutsui ve N. Fujimoto, “Fast QAP Solving by ACO with 2-opt Local Search on a GPU,” IEEE Section Congres, San Francisco, 2011.
18. 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.
19. 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.