On validation of solutions to linear programming problems on cluster computing systems

Authors

DOI:

https://doi.org/10.26089/NumMet.v22r416

Keywords:

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

Abstract

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.

Author Biographies

Leonid B. Sokolinsky

Irina M. Sokolinskaya

References

  1. 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.
  2. T. Hartung, “Making Big Sense from Big Data,” Frontiers in Big Data 1 (2018). doi 10.3389/fdata.2018.00005.
  3. 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.
  4. 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.
  5. 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. doi 10.1007/978-3-319-24024-4_17.
  6. 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.
  7. P. Tar, B. Stagel, and I. Maros, “Parallel Search Paths for the Simplex Algorithm,” Cent. Eur. J. Oper. Res. 25 (4), 967-984 (2017). doi 10.1007/s10100-016-0452-9.
  8. 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. doi 10.1109/WGEC.2009.68.
  9. D. M. Gay, “Electronic Mail Distribution of Linear Programming Test Problems,” Mathematical Programming Society COAL Newsletter 13, 10-12 (1985).
  10. 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.
  11. 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). doi 10.1016/0305-0548(93)90112-V.
  12. 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. doi 10.5555/644108.
  13. T. Koch, “The Final NETLIB-LP Results,” Oper. Res. Lett. 32 (2), 138-142 (2004). doi 10.1016/S0167-6377(03)00094-4.
  14. D. L. Applegate, W. Cook, S. Dash, et al., “Exact Solutions to Linear Programming Problems,” Oper. Res. Lett. 35 (6), 693-699 (2007). doi 10.1016/j.orl.2006.12.010.
  15. 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). doi 10.1134/S0005117912020063].
  16. A. M. Gleixner, D. E. Steffy, and K. Wolter, “Iterative Refinement for Linear Programming,” INFORMS J. Comput. 28 (3), 449-464 (2016).doi 10.1287/ijoc.2016.0692.
  17. L. E. Blumenson, “A Derivation of n-Dimensional Spherical Coordinates,” Am. Math. Mon. 67 (1), 63-66 (1960). doi 10.2307/2308932.
  18. 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.
  19. S. Sahni and G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings,” J. Glob. Optim. 9 (3-4), 357-377 (1996). doi 10.1007/BF00121679.
  20. R. S. Bird, “Lectures on Constructive Functional Programming,” in Constructive Methods in Computing Science (Springer, Heidelberg, 1988), Vol. 55, pp. 151-217.
  21. 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.
  22. L. B. Sokolinsky, “BSF-Skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems,” MethodsX 8 (2019). doi 10.1016/j.mex.2021.101437.
  23. 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.
  24. 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).
    http://ceur-ws.org/Vol-1576/119.pdf
  25. 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). doi 10.14529/cmse210203.

Published

06-11-2021

How to Cite

Соколинский Л.Б., Соколинская И.М. On Validation of Solutions to Linear Programming Problems on Cluster Computing Systems // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2021. 22. 252-262. doi 10.26089/NumMet.v22r416

Issue

Section

Parallel software tools and technologies

Most read articles by the same author(s)