線型計劃法을 위한 非頂邊解法의 硏究

A Review Study on Non-edge Following Algorithms for Linear Programming

This study reviews the solution techniques for Linear Programs which have been proposed after the well-known Simplex method was published in 1947. One group of them are simplex-based ones that include the advanced basis technique, constraint, relaxation technique, multiple pivoting or some ad hoc relaxation called PAPA. Second are the feasible direction search types of Nonlinear Programming solution methods to Linean Programs. Besides these, the theoretical evolution of polynomial-time algorithms including the Khachiyan’s ellipsoid algorithm and the Karmarkar’s projective algorithm is notable in the literatures. As a result of reviews, we conclude that the non-edge following strategies which are common in almost all of the above studies, seems to be promising for improving the computational efficiency over the Simplex Method. We then, investigate the polynomial-time property of the projective algorithm and a feasible direction algorithm with finite convergence which is noted to be more efficient than the Simplex with limited experiences. More research efforts are required on this topic.