AlFaMove: Scalable Implementation of Surface Movement Method for Cluster Computing Systems

Nikolay A. Olkhovsky; Leonid B. Sokolinsky

doi:10.14529/jsfi240301

Authors

Nikolay A. Olkhovsky South Ural State University (National Research University), Chelyabinsk, Russian Federation https://orcid.org/0009-0008-9078-4799
Leonid B. Sokolinsky South Ural State University (National Research University), Chelyabinsk, Russian Federation https://orcid.org/0000-0001-9997-3918

DOI:

https://doi.org/10.14529/jsfi240301

Keywords:

linear programming, surface movement method, numerical implementation, AlFaMove algorithm, parallel implementation, cluster computing system, scalability evaluation

Abstract

The article presents a numerical implementation of the surface movement method for linear programming. The base of this implementation is the new AlFaMove algorithm, which builds on the surface of a feasible polytope an optimal objective path from an arbitrary boundary point to a point that is a solution to a linear programming problem. The optimal objective path is a path along the faces of the feasible polytope in the direction of maximizing the value of the objective function. To calculate the optimal movement direction, the pseudoprojection operation on a linear manifold is used. The pseudoprojection operation is a generalization of the orthogonal projection and is implemented using an iterative projection-type algorithm. The proposition is proved that, for a linear manifold that is the intersection of hyperplanes, the pseudoprojection coincides with the orthogonal projection. It is also proved that, in the case of a linear manifold, pseudoprojection makes it possible to calculate the movement vector in the direction of maximum increase of the objective function. A parallel implementation of the AlFaMove algorithm is described. The results of computational experiments on a cluster computing system are presented to demonstrate the high scalability of the proposed numerical implementation.

References

Boisvert, R.F., Pozo, R., Remington, K.A.: The Matrix Market Exchange Formats: Initial Design. Tech. rep., NISTIR 5935. National Institute of Standards and Technology, Gaithersburg, MD (1996), https://nvlpubs.nist.gov/nistpubs/Legacy/IR/nistir5935.pdf, accessed: 2024-08-26

Branke, J.: Optimization in Dynamic Environments. In: Evolutionary Optimization in Dynamic Environments. Genetic Algorithms and Evolutionary Computation, vol. 3, pp. 13–29. Springer, Boston, MA (2002). https://doi.org/10.1007/978-1-4615-0911-0_2

Dantzig, G.B.: Linear programming and extensions. Princeton university press, Princeton, N.J. (1998)

Fathi, M., Khakifirooz, M., Pardalos, P.M. (eds.): Optimization in Large Scale Problems: Industry 4.0 and Society 5.0 Applications. Springer, Cham, Switzerland (2019). https://doi.org/10.1007/978-3-030-28565-4

Gay, D.M.: Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin 13, 10–12 (1985)

Gould, N.I.: How good are projection methods for convex feasibility problems? Computational Optimization and Applications 40(1), 1–12 (2008). https://doi.org/10.1007/S10589-007-9073-5

Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities - III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1-9, 1969. pp. 159–175. Academic Press, New York, NY, USA (1972)

Kopanos, G.M., Puigjaner, L.: Solving Large-Scale Production Scheduling and Planning in the Process Industries. Springer, Cham, Switzerland (2019). https://doi.org/10.1007/978-3-030-01183-3

Maltsev, A.: The basics of linear algebra. Science. The main editorial office of the phys-math literature, Moskow (1970), (in Russian)

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

Olkhovsky, N.A., Sokolinsky, L.B.: Surface Movement Method for Linear Programming. Lobachevskii Journal of Mathematics 45(10), (in print) (2024)

Schlenkrich, M., Parragh, S.N.: Solving large scale industrial production scheduling problems with complex constraints: an overview of the state-of-the-art. In: Longo, F., Affenzeller, M., Padovano, A., Shen, W. (eds.) 4th International Conference on Industry 4.0 and Smart Manufacturing. Procedia Computer Science. vol. 217, pp. 1028–1037. Elsevier (2023). https://doi.org/10.1016/J.PROCS.2022.12.301

Sokolinskaya, I.M., 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, Switzerland (2017). https://doi.org/10.1007/978-3-319-67035-5_7

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.: BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems. MethodsX 8, Article number 101437 (2021). https://doi.org/10.1016/j.mex.2021.101437

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

Sokolinsky, L.B., Sokolinskaya, I.M.: Apex Method: A New Scalable Iterative Method for Linear Programming. Mathematics 11(7), 1–28 (2023). https://doi.org/10.3390/MATH11071654

Vasin, V.V., Eremin, I.I.: Operators and Iterative Processes of Fej´er Type. Theory and Applications. Inverse and Ill-Posed Problems Series, Walter de Gruyter, Berlin, New York (2009). https://doi.org/10.1515/9783110218190

Voevodin, V., Antonov, A., Nkitenko, D., Shvets, P., Sobolev, S., Sidorov, I., Stefanov, K., Voevodin, V., Zhumatiy, S.: Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community. Supercomputing Frontiers and Innovations 6(2), 4–11 (2019). https://doi.org/10.14529/jsfi190201

Zorkaltsev, V., Mokryi, I.: Interior point algorithms in linear optimization. Journal of applied and industrial mathematics 12(1), 191–199 (2018). https://doi.org/10.1134/S1990478918010179