Tokyo Tech News
Tokyo Institute of Technology merged with Tokyo Medical and Dental University to form Institute of Science Tokyo (Science Tokyo) on October 1, 2024.
Over time, content on this site will be migrated to the Science Tokyo Web. Any information published on this site will be valid in relation to Science Tokyo.
Tokyo Tech News
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.
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
—Creating New Industries and Advancing Civilization—
Information on School of Engineering inaugurated in April 2016
Further information
Professor Shinji Mizuno
School of Engineering
Email mizuno.s.ab@m.titech.ac.jp
Tel +81-3-5734-2816