Research

Tokyo Tech News

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

RSS

Published: February 20, 2017

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.

A sequence of points generated by the simplex method

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 :
Affiliations :
Department of Industrial Engineering and Economics, School of Engineering, Tokyo Institute of Technology.

School of Engineering

School of Engineering
—Creating New Industries and Advancing Civilization—

Information on School of Engineering inaugurated in April 2016

School of Engineering

Schools, Departments, and Institute for Liberal Artsouter

Further information

Professor Shinji Mizuno
School of Engineering

Email mizuno.s.ab@m.titech.ac.jp
Tel +81-3-5734-2816

RSS