VaLiPro: Linear Programming Validator for Cluster Computing Systems
DOI:
https://doi.org/10.14529/jsfi210303Keywords:
linear programming, solution validator, VaLiPro, parallel algorithm, cluster computing system, BSF-skeletonAbstract
The article presents and evaluates a scalable algorithm for validating solutions to linear programming 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.References
Jagadish, H.V., Gehrke, J., Labrinidis, A., et al.: Big data and its technical challenges. Communications of the ACM 57(7), 86–94 (2014). https://doi.org/10.1145/2611567
Hartung, T.: Making Big Sense grom Big Data. Frontiers in Big Data 1, 5 (2018). https://doi.org/10.3389/fdata.2018.00005
Sokolinskaya, I., Sokolinsky, L.B.: On the Solution of Linear Programming Problems in the Age of Big Data. In: Sokolinsky, L., Zymbler, M. (eds.) Parallel Computational Technologies, PCT 2017. Communications in Computer and Information Science, vol. 753. pp. 86–100. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67035-5_7
Mamalis, B., Pantziou, G.: Advances in the Parallelization of the Simplex Method. In: Zaroliagis, C., Pantziou, G., Kontogiannis, S. (eds.) Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295. pp. 281–307. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24024-4_17
Huangfu, Q., Hall, J.A.J.: Parallelizing the dual revised simplex method. Mathematical Programming Computation 10(1), 119–142 (2018). https://doi.org/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 25(4), 967–984 (2017). https://doi.org/10.1007/s10100-016-0452-9
Yang, L., Li, T., Li, J.: Parallel predictor-corrector interior-point algorithm of structured optimization problems. In: 3rd International Conference on Genetic and Evolutionary Computing, WGEC 2009. pp. 256–259 (2009). https://doi.org/10.1109/WGEC.2009.68
Sokolinsky, L.B., Sokolinskaya, I.M.: Scalable Method for Linear Optimization of Industrial Processes. In: Proceedings - 2020 Global Smart Industry Conference, GloSIC 2020. pp. 20–26. Article number 9267854. IEEE (2020). https://doi.org/10.1109/GloSIC50886.2020.9267854
Sokolinskaya, I., Sokolinsky, L.B.: Scalability Evaluation of NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems. In: Voevodin, V., Sobolev, S. (eds.) Supercomputing, RuSCDays 2017. Communications in Computer and Information Science, vol. 793. pp. 40–53. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71255-0_4
Gay, D.M.: Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin (13), 10–12 (1985)
Dhiflaoui, M., Funke, S., Kwappik, C., et al.: Certifying and Repairing Solutions to Large LPs How Good are LP-solvers? In: SODA’03: Proceedings of the fourteenth annual ACMSIAM symposium on Discrete algorithms. pp. 255–256. Society for Industrial and Applied Mathematics, USA (2003)
Rose, D.J., Tarjan, R.E.: Algorithmic Aspects of Vertex Elimination on Directed Graphs. SIAM Journal on Applied Mathematics 34(1), 176–197 (1978). https://doi.org/10.1137/0134014
Bareiss, E.H.: Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation 22(103), 565 (1968). https://doi.org/10.2307/2004533
Middeke, J., Jeffrey, D.J., Koutschan, C.: Common Factors in Fraction-Free Matrix Decompositions. Mathematics in Computer Science 1–20 (2020). https://doi.org/10.1007/s11786-020-00495-9
Wiedemann, D.H.: Solving Sparse Linear Equations over Finite Fields. IEEE Transactions on Information Theory 32(1), 54–62 (1986). https://doi.org/10.1109/TIT.1986.1057137
Koch, T.: The final NETLIB-LP results. Operations Research Letters 32(2), 138–142 (2004). https://doi.org/10.1016/S0167-6377(03)00094-4
Applegate, D.L., Cook, W., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Operations Research Letters 35(6), 693–699 (2007). https://doi.org/10.1016/j.orl.2006.12.010
The GNU Multiple Precision Arithmetic Library. https://gmplib.org
Panyukov, A.V., Gorbik, V.V.: Using massively parallel computations for absolutely precise solution of the linear programming problems. Automation and Remote Control 73(2), 276–290 (2012). https://doi.org/10.1134/S0005117912020063
Gleixner, A.M., Steffy, D.E., Wolter, K.: Iterative refinement for linear programming. INFORMS Journal on Computing 28(3), 449–464 (2016). https://doi.org/10.1287/ijoc.2016.0692
Blumenson, L.E.: A Derivation of n-Dimensional Spherical Coordinates. The American Mathematical Monthly 67(1), 63–66 (1960). https://doi.org/10.2307/2308932
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 149, 193–206 (2021). https://doi.org/10.1016/j.jpdc.2020.12.009
Sokolinsky, L.B.: Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors. Lobachevskii Journal of Mathematics 39(4), 571–575 (2018). https://doi.org/10.1134/S1995080218040121
Sahni, S., Vairaktarakis, G.: The master-slave paradigm in parallel computer and industrial settings. Journal of Global Optimization 9(3-4), 357–377 (1996). https://doi.org/10.1007/BF00121679
Bird, R.S.: Lectures on Constructive Functional Programming. In: Broy, M. (ed.) Constructive Methods in Computing Science. NATO ASI Series F: Computer and Systems Sciences, vol. 55. pp. 151–216. Springer, Berlin, Heidelberg (1988)
Sokolinsky, L.B.: BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems. MethodsX 8. Art. no. 101437 (2021). https://doi.org/10.1016/j.mex.2021.101437
Gropp, W.: MPI 3 and Beyond: Why MPI is Successful and What Challenges It Faces. In: Traff, J.L., Benkner, S., Dongarra, J.J. (eds.) Recent Advances in the Message Passing Interface, EuroMPI 2012. Lecture Notes in Computer Science, vol. 7490. pp. 1–9. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33518-1_1
Kostenetskiy, P., Semenikhina, P.: SUSU Supercomputer Resources for Industry and Fundamental Science. In: Proceedings - 2018 Global Smart Industry Conference, GloSIC 2018, art. no. 8570068. p. 7. IEEE (2018). https://doi.org/10.1109/GloSIC.2018.8570068
Sokolinsky, L.B., Sokolinskaya, I.M.: FRaGenLP: A Generator of Random Linear Programming Problems for Cluster Computing Systems. In: Sokolinsky L., Zymbler M. (eds) Parallel Computational Technologies, PCT 2021. Communications in Computer and Information Science, vol 1437. pp. 164–177. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81691-9_12
Downloads
Published
How to Cite
Issue
License
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-Non Commercial 3.0 License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.