On validation of solutions to linear programming problems on cluster computing systems
Keywords:linear programming, solution validator, VaLiPro, parallel algorithm, cluster computing system, BSF-skeleton
The paper presents and evaluates a scalable algorithm for validating solutions to linear programming (LP) problems on cluster computing systems. The main idea of the method is to generate a regular set of points (validation set) on a small-radius hypersphere centered at the solution point submitted to validation. The objective function is computed at each point of the validation that belongs to the feasible region. If all the values are less than or equal to the value of the objective function at the point that is to be validated, then this point is the correct solution. The parallel implementation of the VaLiPro algorithm is written 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 VaLiPro algorithm.
- H. V. Jagadish, J. Gehrke, A. Labrinidis, et al., “Big Data and Its Technical Challenges,” Commun. ACM 57 (7), 86-94 (2014). doi 10.1145/2611567.
- T. Hartung, “Making Big Sense from Big Data,” Frontiers in Big Data 1 (2018).
- I. M. Sokolinskaya and L. B. Sokolinsky, “On the Solution of Linear Programming Problem in the Era of Big Data,” in Proc. Int. Conf. on Parallel Computational Technologies, Kazan, Russia, April 3-7, 2017 (South Ural State Univ., Chelyabinsk, 2017), pp. 471-484.
- I. M. Sokolinskaya and L. B. Sokolinsky, “Study of the Scalability of the Apex Method for Solving Large-Scale Linear Programming Problems on Cluster Computing Systems,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 21-22, 2020 (MAKS Press, Moscow, 2020), pp. 49-59.
- B. Mamalis and G. Pantziou, “Advances in the Parallelization of the Simplex Method,” in Lecture Notes in Computer Science (Springer, Cham, 2015), Vol. 9295, pp. 281-307.
- Q. Huangfu and J. A. J. Hall, “Parallelizing the Dual Revised Simplex Method,” Math. Prog. Comp. 10 (1), 119-142 (2018). doi 10.1007/s12532-017-0130-5.
- P. Tar, B. Stagel, and I. Maros, “Parallel Search Paths for the Simplex Algorithm,” Cent. Eur. J. Oper. Res. 25 (4), 967-984 (2017).
- L. Yang, T. Li, and J. Li, “Parallel Predictor-Corrector Interior-Point Algorithm of Structured Optimization Problems,” in Proc. 3rd Int. Conf. on Genetic and Evolutionary Computing, Gulin, China, October 14-17, 2009 (IEEE Press, New York, 2009), pp. 256-259.
- D. M. Gay, “Electronic Mail Distribution of Linear Programming Test Problems,” Mathematical Programming Society COAL Newsletter 13, 10-12 (1985).
- A. Charnes, W. M. Raike, J. D. Stutz, et al., “On Generation of Test Problems for Linear Programming Codes,” Commun. ACM 17 (10), 583-586 (1974). doi 10.1145/355620.361173.
- J. L. Arthur and J. O. Frendewey, “GENGUB: A Generator for Linear Programs with Generalized upper Bound Constraints,” Comput. Oper. Res. 20 (6), 565-573 (1993).
- M. Dhiflaoui, S. Funke, C. Kwappik, et al., “Certifying and Repairing Solutions to Large LPs: How Good are LP-solvers?’’ in Proc. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, USA, January 12—14, 2003 (SIAM Press, Philadelphia, 2003), pp. 255-256.
- T. Koch, “The Final NETLIB-LP Results,” Oper. Res. Lett. 32 (2), 138-142 (2004).
- D. L. Applegate, W. Cook, S. Dash, et al., “Exact Solutions to Linear Programming Problems,” Oper. Res. Lett. 35 (6), 693-699 (2007).
- A. V. Panyukov and V. V. Gorbik, “Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems,” Avtom. Telemekh., No. 2, 73-88 (2012) [Autom. Rem. Contr. 73 (2), 276-290 (2012).
- A. M. Gleixner, D. E. Steffy, and K. Wolter, “Iterative Refinement for Linear Programming,” INFORMS J. Comput. 28 (3), 449-464 (2016).
- L. E. Blumenson, “A Derivation of n-Dimensional Spherical Coordinates,” Am. Math. Mon. 67 (1), 63-66 (1960).
- L. B. Sokolinsky, “BSF: A Parallel Computation Model for Scalability Estimation of Iterative Numerical Algorithms on Cluster Computing Systems,” J. Parallel Distrib. Comput. 149, 193-206 (2021). doi 10.1016/j.jpdc.2020.12.009.
- S. Sahni and G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings,” J. Glob. Optim. 9 (3-4), 357-377 (1996).
- R. S. Bird, “Lectures on Constructive Functional Programming,” in Constructive Methods in Computing Science (Springer, Heidelberg, 1988), Vol. 55, pp. 151-217.
- L. B. Sokolinsky, Parallel Algorithmic Skeleton BSF , Certificate of RF Registration of Computer Program No. 2 020 661 344.Date of Registration: September 22, 2020.
- L. B. Sokolinsky, “BSF-Skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems,” MethodsX 8 (2019).
- W. Gropp, “MPI 3 and Beyond: Why MPI is Successful and What Challenges It Faces,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2012), Vol. 7490, pp. 1-9.doi 10.1007/978-3-642-33518-1_1.
- P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computational Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. Vol. 1576, pp. 561-573 (2016).
- I. M. Sokolinskaya and L. B. Sokolinsky, “On Generator of Random Problems for Linear Programming on Cluster Computing Systems,” Vestn. Yuzhn. Ural. Gos. Univ. Ser. Vychisl. Mat. Inf. 10 (2), 38-52 (2021).
How to Cite
Copyright (c) 2021 Л.Б. Соколинский, И.М. Соколинская
This work is licensed under a Creative Commons Attribution 4.0 International License.