On Calculating a Vertex of Feasible Solutions Polytope of Linear Constraints System

Бесплатный доступ

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.

Еще

Linear constraints, feasible solutions polytope, vertex calculation, projection method, VeSP algorithm

Короткий адрес: https://sciup.org/147252008

IDR: 147252008   |   УДК: 519.852, 514.172.45, 519.168   |   DOI: 10.14529/cmse250301