An improved initial basis for the Simplex algorithm

摘要

A lot of research has been done to find a faster (polynomial) algorithm that can solve linear programming (LP) problems. The main branch of this research has been devoted to interior point methods (IPM). The IPM outperforms the Simplex method in large LPs. However, there is still much research being done in order to improve pivoting algorithms. In this paper, we present a new approach to the problem of improving the pivoting algorithms: instead of starting the Simplex with the canonical basis, we suggest as initial basis a vertex of the feasible region that is much closer to the optimal vertex than the initial solution adopted by the Simplex. By supplying the Simplex with a better initial basis, we were able to improve the iteration number efficiency of the Simplex algorithm in about 33%.