Optimization Online


A Strongly Polynomial Simplex Method for Totally Unimodular LP

Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)

Abstract: 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.

Keywords: Linear programming, Simplex method, Strongly polynomial, Totally unimodular

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

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

Download: [PDF]

Entry Submitted: 07/21/2014
Entry Accepted: 07/21/2014
Entry Last Modified: 08/19/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society