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 for solving linear programming problems, but it is theoretically unknown whether it is a polynomial or strongly-polynomial .

É. 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.


Explore further

The complexity and security of a widely-used cryptography scheme are lower than previously thought

More information: S. Mizuno. The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption, Optimization Methods and Software (2016). DOI: 10.1080/10556788.2016.1208748
Citation: Strong polynomiality of the simplex method for totally unimodular linear programming problems (2017, February 28) retrieved 19 June 2019 from https://phys.org/news/2017-02-strong-polynomiality-simplex-method-totally.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
4 shares

Feedback to editors

User comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more