VaLiPro: Linear Programming Validator for Cluster Computing Systems


  • Leonid B. Sokolinsky South Ural State University
  • Irina M. Sokolinskaya South Ural State University



linear programming, solution validator, VaLiPro, parallel algorithm, cluster computing system, BSF-skeleton


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.


Jagadish, H.V., Gehrke, J., Labrinidis, A., et al.: Big data and its technical challenges. Communications of the ACM 57(7), 86–94 (2014).

Hartung, T.: Making Big Sense grom Big Data. Frontiers in Big Data 1, 5 (2018).

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).

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).

Huangfu, Q., Hall, J.A.J.: Parallelizing the dual revised simplex method. Mathematical Programming Computation 10(1), 119–142 (2018).

Tar, P., Stagel, B., Maros, I.: Parallel search paths for the simplex algorithm. Central European Journal of Operations Research 25(4), 967–984 (2017).

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).

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).

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).

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).

Bareiss, E.H.: Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation 22(103), 565 (1968).

Middeke, J., Jeffrey, D.J., Koutschan, C.: Common Factors in Fraction-Free Matrix Decompositions. Mathematics in Computer Science 1–20 (2020).

Wiedemann, D.H.: Solving Sparse Linear Equations over Finite Fields. IEEE Transactions on Information Theory 32(1), 54–62 (1986).

Koch, T.: The final NETLIB-LP results. Operations Research Letters 32(2), 138–142 (2004).

Applegate, D.L., Cook, W., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Operations Research Letters 35(6), 693–699 (2007).

The GNU Multiple Precision Arithmetic Library.

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).

Gleixner, A.M., Steffy, D.E., Wolter, K.: Iterative refinement for linear programming. INFORMS Journal on Computing 28(3), 449–464 (2016).

Blumenson, L.E.: A Derivation of n-Dimensional Spherical Coordinates. The American Mathematical Monthly 67(1), 63–66 (1960).

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).

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).

Sahni, S., Vairaktarakis, G.: The master-slave paradigm in parallel computer and industrial settings. Journal of Global Optimization 9(3-4), 357–377 (1996).

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).

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).

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).

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).




How to Cite

Sokolinsky, L. B., & Sokolinskaya, I. M. (2021). VaLiPro: Linear Programming Validator for Cluster Computing Systems. Supercomputing Frontiers and Innovations, 8(3), 51–61.