On Calculating a Vertex of Feasible Solutions Polytope of Linear Constraints System
DOI:
https://doi.org/10.14529/cmse250301Keywords:
linear constraints, feasible solutions polytope, vertex calculation, projection method, VeSP algorithmAbstract
The article is devoted to a new algorithm for calculating a vertex of polytope being the feasible region of linear constraint system. The algorithm called VeSP starts at an arbitrary point of the polytope and, moving along its faces, stops at some vertex. To calculate the movement direction along the face, it uses the projection method. The idea of this method is as follows. For the current approximation point, an affine subspace is calculated, which is the affine hull of the face containing the point. A non-zero vector is added to the current approximation point. This gives an external point relative to the current affine subspace. The orthogonal projection of the external point onto the current affine subspace is calculated using a known analytical formula. The projection point determines the direction of movement along the edge to its boundary, which gives the next approximation point. Each movement reduces the dimension of the current face. Thus, we arrive at a zero-dimensional face, which is the vertex of the polytope. A formal description of the VeSP algorithm is provided. The convergence of the VeSP algorithm to a polytope vertex in a finite number of iterations is proved. This number does not exceed the space dimension. An information about the implementation of the VeSP algorithm in C++ is provided. The results of computational experiments with real problems from the Netlib-LP collection are described. For all test problems, the VeSP algorithm successfully found the vertex of the polytope in a finite number of iterations that did not exceed the space dimension. For most problems, finding the vertex took less than one second on a commodity personal computer.References
Dantzig G.B. Linear programming and extensions. Princeton, N.J.: Princeton university press, 1998. 656 p.
Zhulev A., Sokolinsky L. AlEM: a new parallel algorithm for linear programming on cluster computing systems. PREPRINTS.RU. 2025. P. 1–19. (in Russian) DOI: 10.24108/preprints-3113529.
Avis D. A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm. Polytopes - Combinatorics and Computation. DMV Seminar, vol 29 / ed. by G. Kalai, G. Ziegler. Basel: Birkhauser, 2000. P. 177–198. DOI: 10.1007/978-3-0348-8438-9_9.
Assad C.L., Morales G., Arica J. Vertex Enumeration of Polyhedra. Pesquisa Operacional. 2022. Vol. 42: e25457. P. 1–20. DOI: 10.1590/0101-7438.2022.042.00254570.
Schrijver A. Theory of Linear and Integer Programming. Chichester, New York, Brisbane, Tofonfo, Singapore: Wiley, Sons, 1998. 484 p.
Klee V., Minty G.J. How good is the simplex algorithm?. Inequalities - III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1-9, 1969 / ed. by O. Shisha. New York, NY, USA: Academic Press, 1972. P. 159–175.
Khachiyan L. Fourier–Motzkin Elimination Method. Encyclopedia of Optimization / ed. by C. Floudas, P. Pardalos. Boston, MA: Springer, 2008. P. 1074–1077. DOI: 10.1007/978-0-387-74759-0_187.
Duffin R.J. On fourier’s analysis of linear inequality systems. Pivoting and Extensions / ed. by M. Balinski. Berlin, Heidelberg: Springer, 1974. P. 71–95. DOI: 10.1007/BFB0121242.
Motzkin T.S. Contributions to the Theory of Linear Inequalities. Theodore S. Motzkin: Selected Papers / ed. by D. Cantor, B. Gordon, B.L. Rothschild. Boston: Birkhauser, 1983. P. 1–80.
Gritzmann P., Klee V. Mathematical Programming and Convex Geometry. Handbook of Convex Geometry, Vol. A / ed. by P.M. Gruber, J.M. Wills. Amsterdam: Elsevier, 1993. P. 627–674.
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.
Murty K.G. Computational and Algorithmic Linear Algebra and n-Dimensional Geometry. World Scientific, 2011. xxi, 552 p. DOI: 10.1142/8261.
Kaczmarz S. Approximate solution of systems of linear equations. International Journal of Control. 1993. Vol. 57, no. 6. P. 1269–1271. DOI: 10.1080/00207179308934446.
Chen X. The Kaczmarz algorithm, row action methods, and statistical learning algorithms. Frames and Harmonic Analysis. Contemporary Mathematics, vol. 706 / ed. by Y. Kim, S. Narayan, G. Picioroaga, E. Weber. Providence, Rhode Island: American Mathematical Society, 2018. P. 115–128. DOI: 10.1090/CONM/706.
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., Sokolinsky L. Visualizing Multidimensional Linear Programming Problems. Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science, vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2022. P. 172–196. DOI: 10.1007/978-3-031-11623-0_13.
Agmon S. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. Vol. 6. P. 382–392. DOI: 10.4153/CJM-1954-037-2.
Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. Vol. 6. P. 393–404. DOI: 10.4153/CJM-1954-038-x.
Gay D.M. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin. 1985. Vol. 13. P. 10–12.
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.
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.
Deutsch F. Rate of Convergence of the Method of Alternating Projections. Parametric Optimization and Approximation / ed. by B. Brosowski, F. Deutsch. Basel: Birkhauser Verlag, 1985. P. 96–107. DOI: 10.1007/978-3-0348-6253-0_7.
