О генерации случайных задач линейного программирования на кластерных вычислительных системах
Автор: Соколинский Леонид Борисович, Соколинская Ирина Михайловна
Статья в выпуске: 2 т.10, 2021 года.
Бесплатный доступ
В статье рассматривается масштабируемый алгоритм FRaGenLP для генерации больших совместных случайных задач линейного программирования произвольной размерности n на кластерных вычислительных системах. Для обеспечения совместности и ограниченности допустимой области система ограничений включает в себя 2n+1 стандартных неравенств, называемых опорными. Случайные неравенства добавляются в систему последовательно так, чтобы сохранялась совместность ограничений. Кроме этого, вводятся две метрики «похожести», которые препятствуют добавлению нового случайного неравенства, «похожего» на какое-либо из уже включенных в систему, включая опорные. Также отклоняются случайные неравенства, которые при фиксированной целевой функции не влияют на решение опорной задачи линейного программирования. Параллельная реализация алгоритма FRaGenLP выполнена на языке C++ с использованием параллельного BSF-каркаса, инкапсулирующего в проблемно-независимой части своего кода все аспекты, связанные с распараллеливанием программы на базе библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе, подтверждающие эффективность использованного подхода.
Случайная задача линейного программирования, генератор задач, FRaGenLP, кластерные вычислительные системы, BSF-каркас
Короткий адрес: https://sciup.org/147234293
IDR: 147234293 | DOI: 10.14529/cmse210203
Список литературы О генерации случайных задач линейного программирования на кластерных вычислительных системах
- Jagadish H.V. et al. Big data and its technical challenges // Communications of the ACM. 2014. Vol. 57, no. 7. P. 86-94. DOI: 10.1145/2611567.
- Hartung T. Making Big Sense From Big Data // Frontiers in Big Data. 2018. Vol. 1. P. 5. DOI: 10.3389/fdata.2018.00005.
- Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии (ПаВТ'2017): Труды XI международной научной конференции (Казань, 3-7 апреля 2017 г.). Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. С. 471-484.
- Соколинский Л.Б., Соколинская И.М. Исследование масштабируемости апекс-метода для решения сверхбольших задач линейного программирования на кластерных вычислительных системах // Суперкомпьютерные дни в России: Труды международной конференции (Москва, 21-22 сентября 2020 г.). Москва: МАКС Пресс, 2020. C. 49-59.
- Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method // Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science. Cham: Springer, 2015. Vol. 9295. P. 281-307. DOI: 10.1007/978-3-319-24024-4_17.
- Huangfu Q., Hall J.A.J. Parallelizing the dual revised simplex method // Mathematical Programming Computation. Springer Verlag, 2018. Vol. 10, no. 1. P. 119-142. DOI: 10.1007/s12532-017-0130-5.
- Tar P., Stagel B., Maros I. Parallel search paths for the simplex algorithm // Central European Journal of Operations Research. Springer Verlag, 2017. Vol. 25, no. 4. P. 967984. DOI: 10.1007/s10100-016-0452-9.
- Yang L., Li T., Li J. Parallel predictor-corrector interior-point algorithm of structured optimization problems // 3rd International Conference on Genetic and Evolutionary Computing, WGEC 2009. 2009. P. 256-259. DOI: 10.1109/WGEC.2009.68.
- Gay D.M. Electronic mail distribution of linear programming test problems // Mathematical Programming Society COAL Bulletin. 1985. no. 13. P. 10-12.
- Charnes A. et al. On Generation of Test Problems for Linear Programming Codes // Communications of the ACM. 1974. Vol. 17, no. 10. P. 583-586. DOI: 10.1145/355620.361173.
- Arthur J.L., Frendewey J.O. GENGUB: A generator for linear programs with generalized upper bound constraints // Computers and Operations Research. Pergamon, 1993. Vol. 20, no. 6. P. 565-573. DOI: 10.1016/0305-0548(93)90112-V.
- Castillo E., Pruneda R.E., Esquivel Mo. Automatic generation of linear programming problems for computer aided instruction // International Journal of Mathematical Education in Science and Technology. Taylor & Francis Group, 2001. Vol. 32, no. 2. P. 209-232. DOI: 10.1080/00207390010010845.
- Dhiflaoui M. et al. Certifying and Repairing Solutions to Large LPs How Good are LP-solvers? // SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. USA: Society for Industrial and Applied Mathematics, 2003. P. 255256.
- Desmos Graphing Calculator. URL: https://www.desmos.com/calculator (дата обращения: 09.03.2021).
- Sokolinsky L.B. BSF: A parallel computation model for scalability estimation of iterative numerical algorithms on cluster computing systems // Journal of Parallel and Distributed Computing. 2021. Vol. 149. P. 193-206. DOI: 10.1016/j.jpdc.2020.12.009.
- Sahni S., Vairaktarakis G. The master-slave paradigm in parallel computer and industrial settings // Journal of Global Optimization. 1996. Vol. 9, no. 3-4. P. 357-377. DOI:10.1007/BF00121679.
- Sokolinsky L.B. BSF-skeleton. User manual: arXiv:2008.12256 [cs.DC]. 2020. 22 p.
- Sokolinsky L.B. BSF-skeleton. 2019. URL: https://github.com/leonid-sokolinsky/BSF-skeleton (дата обращения: 09.03.2021).
- Gropp W. MPI 3 and Beyond: Why MPI Is Successful and What Challenges It Faces // Recent Advances in the Message Passing Interface. EuroMPI 2012. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2012. Vol. 7490. P. 1-9. DOI: 10.1007/978-3-642-33518-1_1.
- Bird R.S. Lectures on Constructive Functional Programming // Constructive Methods in Computing Science. NATO ASI Series F: Computer and Systems Sciences. Berlin, Heidlberg: Springer, 1988. Vol. 55. P. 151-216.
- Kostenetskiy P.S., Safonov A.Y. SUSU Supercomputer Resources // Proceedings of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). CEUR Workshop Proceedings. Vol. 1576. 2016. P. 561-573.
