A Strongly Polynomial Simplex Method for Totally Unimodular LP

Kitahara and Mizuno get new bounds for the number of distinct solutions generated by the simplex method for linear programming (LP). In this paper, we combine results of Kitahara and Mizuno and Tardos's strongly polynomial algorithm, and propose an algorithm for solving a standard form LP problem. The algorithm solves polynomial number of artificial LP problems by the simplex method with Dantzig's rule. It is shown that the total number of distinct basic solutions generated by the algorithm is polynomially bounded in the number of constraints, the number of variables, and the maximum determinant of submatrices of a coefficient matrix. If the coefficient matrix is totally unimodular and all the artificial problems are nondegenerate, then the algorithm is strongly polynomial.

Citation

Technical Report 2014-3, Department of Industrial Engineering and Management, Tokyo Institute of Technology

Article

Download

View A Strongly Polynomial Simplex Method for Totally Unimodular LP