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

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

Authors

  • Leonid B. Sokolinsky
  • Irina M. Sokolinskaya

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.

Downloads

Published

2021-11-06

Issue

Vol. 22 (2021): Issue 4.

Section

Parallel software tools and technologies

Author Biographies

Leonid B. Sokolinsky

South Ural State University (National Research University),
• Professor, Vice Rector

Irina M. Sokolinskaya

South Ural State University (National Research University),
• Associate Professor

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

License

Copyright (c) 2021 Л.Б. Соколинский, И.М. Соколинская

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.