On Generator of Random Problems for Linear Programming on Cluster Computing Systems

Leonid B. Sokolinsky, Irina M. Sokolinskaya

Abstract


The article presents and evaluates a scalable FRaGenLP algorithm for generating random linear programming problems of large dimension n on cluster computing systems. To ensure the consistency of the problem and the boundedness of the feasible region, the constraint system includes 2n+1 standard inequalities, called support inequalities. New random inequalities are generated and added to the system in a manner that ensures the consistency of the constraints. Furthermore, the algorithm uses two likeness metrics to prevent the addition of a new random inequality that is similar to one already present in the constraint system. The algorithm also rejects random inequalities that cannot affect the solution of the linear programming problem bounded by the support inequalities. The parallel implementation of the FRaGenLP algorithm is performed in C++ through the parallel BSF-skeleton, which encapsulates all aspects related to the MPI-based parallelization of the program. We provide the results of large-scale computational experiments on a cluster computing system to study the scalability of the FRaGenLP algorithm.


Keywords


random linear programming problem; problem generator; FRaGenLP; cluster computing systems; BSF-skeleton

References


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