Strong polynomiality of the simplex method for totally unimodular linear programming problems

Linear programming is the most fundamental optimization problem with applications in many areas including engineering, management, and economics.

The simplex method is a practical and efficient algorithm for solving linear programming problems, but it is theoretically unknown whether it is a polynomial or strongly-polynomial algorithm.

É. Tardos of Cornell University proposed a strongly polynomial algorithm for combinatorial linear programming problems and T. Kitahara and S. Mizuno at Tokyo Institute of Technology have obtained a new bound for the number of distinct solutions generated by the simplex method.

It is known that the simplex method requires an exponential number of iterations for some special linear programming instances. Hence the method is neither polynomial nor a strongly-polynomial algorithm for general linear programming problems.

The researchers showed that the simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular linear programming problems, if the problems are nondegenerate.

These findings give a theoretical background as to why the simplex method could solve a large scale linear programming problem efficiently.

Figure. A sequence of points generated by the simplex method

Reference

Authors:	Shinji Mizuno.
Title of original paper:	The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption.
Journal:	Optimization Methods and Software, Vol. 31, 1298-1304 (2016).
DOI :	10.1080/10556788.2016.1208748
Affiliations :	Department of Industrial Engineering and Economics, School of Engineering, Tokyo Institute of Technology.

• Mizuno Laboratory
• Researcher Profile | Tokyo Tech STAR Search - Shinji Mizuno
• Department of Industrial Engineering and Economics, School of Engineering
• Latest Research News