Letter to the Editor---A Conjecture Concerning the Smallest Bound on the Iterations in Linear Programming

T. L. Saaty
Additional contact information
T. L. Saaty: Office of Naval Research, Washington, D. C.

Operations Research, 1963, vol. 11, issue 1, 151-153

Abstract: In solving linear programming problems accurate estimates of the number of iterations needed to reach the optimum are important to have. It has been mentioned in the literature that computing experience indicates this number of iterations to be of the order of twice the number of constraints. We have been informed by two computing groups that a number of large linear programming problems have been left unsolved because, after many hours of machine operation, it was not known how much longer the process would continue. Here through heuristic arguments based on what appears to be a reasonable conjecture we give an upper bound to the number of iterations for algorithms which change one vector at a time, such as the simplex process.

Date: 1963
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.11.1.151 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:11:y:1963:i:1:p:151-153

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().