О генерации случайных задач линейного программирования на кластерных вычислительных системах

Леонид Борисович Соколинский, Ирина Михайловна Соколинская

Аннотация


В статье рассматривается масштабируемый алгоритм FRaGenLP для генерации больших совместных случайных задач линейного программирования произвольной размерности n на кластерных вычислительных системах. Для обеспечения совместности и ограниченности допустимой области система ограничений включает в себя 2n+1 стандартных неравенств, называемых опорными. Случайные неравенства добавляются в систему последовательно так, чтобы сохранялась совместность ограничений. Кроме этого, вводятся две метрики «похожести», которые препятствуют добавлению нового случайного неравенства, «похожего» на какое-либо из уже включенных в систему, включая опорные. Также отклоняются случайные неравенства, которые при фиксированной целевой функции не влияют на решение опорной задачи линейного программирования. Параллельная реализация алгоритма FRaGenLP выполнена на языке C++ с использованием параллельного BSF-каркаса, инкапсулирующего в проблемно-независимой части своего кода все аспекты, связанные с распараллеливанием программы на базе библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе, подтверждающие эффективность использованного подхода.

Ключевые слова


случайная задача линейного программирования; генератор задач; FRaGenLP; кластерные вычислительные системы; BSF-каркас

Полный текст:

PDF

Литература


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.

Sokolinskaya I.M., Sokolinsky L.B. On solving the linear programming problem in the era of big data. Parallel Computational Technologies (PCT’2017): Proceedings of the 11th International Scientific Conference (Kazan, April, 3–7, 2017). Short papers and posters. Chelyabinsk: SUSU Publishing Center, 2017. P. 471–484. (in Russian)

Sokolinsky L.B., Sokolinskaya I.M. Study of the scalability of the apex method for solving ultra-large linear programming problems on cluster computing systems. Russian Supercomputer Days: Proceedings of the Conference (Moscow, September, 21–22, 2020). Moscow, MAKS Press, 2020. P. 49–59. (in Russian)

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., Stágel B., Maros I. Parallel search paths for the simplex algorithm. Central European Journal of Operations Research. Springer Verlag, 2017. Vol. 25, no. 4. P. 967–984. 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 Mó. 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 LPsolvers? SODA ’03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. USA: Society for Industrial and Applied Mathematics, 2003. P. 255–256.

Desmos Graphing Calculator. URL: https://www.desmos.com/calculator (accessed: 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 (accessed: 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.




DOI: http://dx.doi.org/10.14529/cmse210203