On Projection Method of Linear Programming
DOI:
https://doi.org/10.14529/cmse260101Keywords:
linear programming, HAlEM algorithm, projection method, parallel implementation, MPI, cluster computing system, scalability evaluation, Netlb-LPAbstract
The paper addresses the problem of developing efficient projection-type methods for linear programming (LP). A new hybrid projection algorithm called HAlEM (Hybrid Along Edges Movement) is proposed, combining ideas from the projection approach and the simplex method. The algorithm starts from an arbitrary vertex of the feasible solution polytope and moves along its edges toward the optimal vertex. An original two-factor projection method is used to compute the direction of movement, ensuring high computational accuracy for any LP problem. The main advantage of HAlEM over previous projection algorithms (AlFaMove, AlEM) is its avoidance of exhaustive combinatorial enumeration of all possible combinations of hyperplanes by employing a matrix basis update technique borrowed from the simplex method. This allows one to circumvent exponential computational complexity. The paper presents a parallel version of the algorithm based on the BSF parallel computing model and a master-worker scheme, enabling an efficient implementation for cluster-type supercomputer systems. Computational experiments were conducted on benchmark problems from the Netlib-LP repository and on a series of parameterized problems. The experimental results demonstrate that HAlEM, unlike the simplex method, possesses a higher degree of parallelism, allowing the efficient use of up to several dozen processor nodes, and exhibits good scalability with parallel efficiency not falling below 51%. Furthermore, the algorithm provides high computational accuracy at the level of machine epsilon.References
Pan P.-Q. Linear Programming Computation. Berlin, Heidelberg: Springer, 2014. 747 p. DOI: 10.1007/978-3-642-40754-3.
Bixby R.E. Solving Real-World Linear Programs: A Decade and More of Progress. Operations Research. 2002. Vol. 50, no. 1. P. 3–15. DOI: 10.1287/opre.50.1.3.17780.
Rasmussen S. Production Economics. The Basic Theory of Production Optimisation. 2nd ed. Berlin, Heidelberg: Springer, 2013. XII, 292 p. Springer Texts in Business and Economics. DOI: 10.1007/978-3-642-30200-8.
Xu Y. Solving Large Scale Optimization Problems in the Transportation Industry and Beyond Through Column Generation. Optimization in Large Scale Problems. Springer Optimization and Its Applications, vol. 152. Cham: Springer, 2019. P. 269–292. DOI: 10.1007/978-3-030-28565-4_23.
Chung W. Applying large-scale linear programming in business analytics. 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2015. P. 1860–1864. DOI: 10.1109/IEEM.2015.7385970.
Gondzio J., Gruca J.A., Hall J.A.J., et al. Solving large-scale optimization problems related to Bell’s Theorem. Journal of Computational and Applied Mathematics. 2014. Vol. 263. P. 392–404. DOI: 10.1016/j.cam.2013.12.003.
Dantzig G.B., Thapa M.N. Linear Programming 2: Theory and Extensions. Springer Series in Operations Research and Financial Engineering. New York, NY, USA: Springer, 2003. XXVI, 448 p. DOI: 10.1007/b97283.
Tolla P. A Survey of Some Linear Programming Methods. Concepts of Combinatorial Optimization / ed. by V.T. Paschos. 2nd ed. Hoboken, NJ, USA: John Wiley, Sons, 2014. Chap. 7. P. 157–188. DOI: 10.1002/9781119005216.ch7.
Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method. Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295 / ed. by C. Zaroliagis, G. Pantziou, S. Kontogiannis. Cham: Springer, 2015. P. 281–307. DOI: 10.1007/978-3-319-24024-4_17.
Im H., Wolkowicz H. Revisiting degeneracy, strict feasibility, stability, in linear programming. European Journal of Operational Research. 2023. Vol. 310, no. 2. P. 495–510. DOI: 10.1016/j.ejor.2023.03.021.
Gass S.I., Vinjamuri S. Cycling in linear programming problems. Computers and Operations Research. 2004. Vol. 31, no. 2. P. 303–311. DOI: 10.1016/S0305-0548(02)00226-5.
Hall J., McKinnon K. The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. Mathematical Programming, Series B. 2004. Vol. 100, no. 1. P. 133–150. DOI: 10.1007/s10107-003-0488-1.
Sokolinsky L.B., Sokolinskaya I.M. Apex Method: A New Scalable Iterative Method for Linear Programming. Mathematics. 2023. Vol. 11, no. 7. P. 1–28. DOI: 10.3390/MATH11071654.
Olkhovsky N.A., Sokolinsky L.B. Surface Movement Method for Linear Programming. Lobachevskii Journal of Mathematics. 2024. Vol. 45, no. 10. P. 5061–5079. DOI: 10.1134/S1995080224605745.
Olkhovsky N.A., Sokolinsky L.B. AlFaMove: Scalable Implementation of Surface Movement Method for Cluster Computing Systems. Supercomputing Frontiers and Innovations. 2024. Vol. 11, no. 3. P. 4–26. DOI: 10.14529/jsfi240301.
Zhulev A.E., Sokolinsky L.B. Finding optimal vertex on polytope of feasible solutions to linear programming problem. Numerical Methods and Programming. 2026. Vol. 27, no. 1. P. 1–18. (in Russian) DOI: 10.26089/NumMet.v27r101.
Murty K.G. Computational and Algorithmic Linear Algebra and n-Dimensional Geometry. Singapore: World Scientific Publishing Company, 2014. 480 p. DOI: 10.1142/8261.
Strang G. Linear Algebra and Its Applications. 2nd. Academic Press, 1980. 425 p.
Schrijver A. Theory of Linear and Integer Programming. Chichester, New York, Brisbane, Toronto, Singapore: Wiley, Sons, 1998. 484 p.
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. 2021. Vol. 149. P. 193–206. DOI: 10.1016/j.jpdc.2020.12.009.
Sokolinsky L.B. BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems. MethodsX. 2021. Vol. 8. Article number 101437. DOI: 10.1016/j.mex.2021.101437.
Dolganina N., Ivanova E., Bilenko R., Rekachinsky A. HPC Resources of South Ural State University. Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science, vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2022. P. 43–55. DOI: 10.1007/978-3-031-11623-0_4.
Gay D.M. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin. 1985. Vol. 13. P. 10–12.
Murtagh B.A. Advanced linear programming: computation and practice. New York, London: McGraw-Hill, 1981. xii, 202 p.
Boisvert R.F., Pozo R., Remington K.A. The Matrix Market Exchange Formats: Initial Design: tech. rep. / NISTIR 5935. National Institute of Standards; Technology. Gaithersburg, MD, 1996. P. 14. URL: https://nvlpubs.nist.gov/nistpubs/Legacy/IR/nistir5935.pdf.
Koch T. The final NETLIB-LP results. Operations Research Letters. 2004. Vol. 32, no. 2. P. 138–142. DOI: 10.1016/S0167-6377(03)00094-4.
Quarteroni A., Sacco R., Saleri F. Numerical Mathematics. Vol. 37. 2nd ed. Berlin, Heidelberg: Springer, 2007. XVIII, 657 p. Texts in Applied Mathematics. DOI: 10.1007/b98885.
Ziegler G.M. Lectures on Polytopes. Vol. 152. New York, NY: Springer New York, 1995. XI, 370 p. Graduate Texts in Mathematics. DOI: 10.1007/978-1-4613-8431-1.
Sokolinsky L.B., Sokolinskaya I.M. FRaGenLP: A Generator of Random Linear Programming Problems for Cluster Computing Systems. Parallel Computational Technologies. PCT 2021. Communications in Computer and Information Science, vol. 1437 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2021. P. 164–177. DOI: 10.1007/978-3-030-81691-9_12.
