EFFECTIVE REALIZATION OF EXACT ALGORITHMS FOR SOLVING DISCRETE OPTIMIZATION PROBLEMS ON GRAPHIC ACCELERATORS
Abstract
Most of the problems of discrete optimization belong to the class of NP-complete problems. This means that algorithms that can find their exact solution, in general, can work with exponential complexity relative to the length of the input data. Thanks to progress, today there are technologies that have not yet been widely used to implement applied optimization methods. Among these technologies is GP GPU (General Purposed Graphical Processing Unit). The application of this technology to well-known algorithms can help to achieve greater efficiency. The purpose of this paper is to investigate the possibilities of using parallel computations on video cards to solve discrete optimization problems. The problem of a one-dimensional Boolean knapsack was chosen as the target problem. To solve the problem, methods for obtaining an exact solution are considered - the full search algorithm, which is the starting point in the study, and the "branches and boundaries" method, which allows to reduce the search by eliminating obviously inappropriate solutions. The algorithms considered are estimated in terms of the number of operations and execution time, implemented in a single-threaded configuration of the central processor, and then parallelized on a video card. Based on the results of these methods, a combined algorithm was created that combines both algorithms to achieve greater efficiency. For parallelizing the calculations on the graphics card, the CUDA technology is chosen. Algorithms are implemented in C. After the implementation of the algorithms, testing was carried out on various data sets and different configurations of the target platform. The results of experimental studies are presented, the acceleration of work is investigated with the use of parallel computations and a comparative analysis of the efficiency of the algorithms is carried out.
References
[2] Kolesar P.J. A Branch and Bound Algorithm for the Knapsack Problem. Management science. 1967; 13(9): 609-772. DOI: 10.1287/mnsc.13.9.723
[3] Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science. 1999; 45(3):297-454. DOI: 10.1287/mnsc.45.3.414
[4] Chu P.C., Beasley J.E. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics. 1998; 4(1):63-86. DOI: 10.1023/A:100964240
[5] Posypkin M.A., Sigal I.K. A combined parallel algorithm for solving the knapsack problem. Journal of Computer and Systems Sciences International. 2008; 47(4):543-551. DOI: 10.1134/S1064230708040072
[6] Harris M. Mapping computational concepts to GPUs. ACM SIGGRAPH 2005 Courses (SIGGRAPH '05), John Fujii (Ed.). ACM, New York, NY, USA, 2005. Article 50. DOI: 10.1145/1198555.1198768
[7] Official programming guide for CUDA, ver. 1.1. CUDA Programming Guide. Chapter 1. Introduction to CUDA → 1.2 CUDA: A New Architecture for Computing on the GPU. Available at: http://developer.download.nvidia.com/compute/cuda/1_1/NVIDIA_CUDA_Programming_Guide_1.1.pdf (accessed 26.04.2018).
[8] Boreskov A.V., Kharlamov A.A., Markovsky N.D. Foreword: Sadovnichiy V.A. Parallel'nye vychisleniya na GPU. Arhitektura i programmnaya model' CUDA [Parallel computing on the GPU. Architecture and software model CUDA]. Moscow: MSU. 2015. 336 p. (In Russian)
[9] Boyer V., El Baz D., Elkihel M. Solving knapsack problems on GPU. Computers & Operations Research. 2012; 39(1):42-47. DOI: 10.1016/j.cor.2011.03.014
[10] Lalami M.E., El-Baz D. GPU Implementation of the branch and bound method for knapsack problems. Proceedings of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Shanghai, China, 2012. pp. 1769-1777. DOI: 10.1109/IPDPSW.2012.219
[11] Kolpakov R.M., Posypkin M.A. On the best choice of a branching variable in the subset sum problem. Discrete Mathematics and Applications. 2018; 28(1):29-34. DOI: 10.1515/dma-2018-0004
[12] Finkelstein Yu.Yu. Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya [Approximate methods and applied problems of discrete programming]. Moscow: Nauka, 1976. 265 p. (In Russian)
[13] Sigal I.K., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye algoritmy [Introduction to Applied Discrete Programming: Models and Computational Algorithms]. Moscow: Fizmatlit, 2007. 304 p. (In Russian)
[14] Keller H., Pfershy U., Pisinger D. Knapsack Problems. Springer, Berlin, Heidelberg, 2004. 548 p. DOI: 10.1007/978-3-540-24777-7
[15] Levitin A.V. Algoritmy: vvedenie v razrabotku i anali [Algorithms: Introduction to Development and Analysis]. M.: Williams Publishing House, 2006. 576 p. (In Russian)
[16] Sedgwick R. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition. Addison-Wesley Professional, 1998. 752 p.
[17] Suri B. Accelerating the knapsack problem on GPUs. Linköping, Sweden, 2011. 87 p.
[18] Ristovski Z. et al. Parallel implementation of the modified subset sum problem in CUDA. Proceedings of 2014 22nd Telecommunications Forum Telfor (TELFOR), Belgrade, 2014. pp. 923-926. DOI: 10.1109/TELFOR.2014.7034556
[19] Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Springer-Verlag Berlin Heidelberg, 2004. 548 p. DOI: 10.1007/978-3-540-24777-7
[20] Jaros J., Pospichal P. A Fair Comparison of Modern CPUs and GPUs Running the Genetic Algorithm under the Knapsack Benchmark. In: Di Chio C. et al. (eds) Applications of Evolutionary Computation. EvoApplications 2012. Lecture Notes in Computer Science, vol. 7248. Springer, Berlin, Heidelberg, 2012. pp. 426-435. DOI: 10.1007/978-3-642-29178-4_43
[21] Li K. et al. A cost-optimal parallel algorithm for the 0-1 knapsack and its performance on multicore CPU and GPU implementations. Parallel Computing. 2015; 43:27-42. DOI: 10.1016/j.parco.2015.01.004
[22] Boukedjar A., Lalami M.E., El-Baz D. Parallel branch and bound on a CPU-GPU system. Proceedings of 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Garching, 2012. pp. 392-398. DOI: 10.1109/PDP.2012.23
[23] Crawford M., Toth D. Parallelization of the Knapsack Problem as an Introductory Experience in Parallel Computing. Journal of Computational Science Education. 2013; 4(1):35-39. DOI: 10.22369/issn.2153-4136/4/1/6
[24] Kolpakov R.M., Posypkin M.A. Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem. Discrete Mathematics and Applications. 2010; 20(1):95-112. DOI: 10.1515/dma.2010.006
[25] Posypkin M.A., Slgal I.Kh. Investigation of algorithms for parallel computations in knapsack-type discrete optimization problems. Computational Mathematics and Mathematical Physics. 2005; 45(10):1735-1742.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
