Papers
Letter to the Editor—A Conjecture Concerning the Smallest Bound on the Iterations in Linear Programming
Author(s)Thomas Saaty
Joseph M. Katz Graduate School of Business
University of Pittsburgh
United States
Publication date: Feb, 1963
Journal: Operations ResearchVol.: 11- Issue: 1- Pages: 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.
Keywords: Linear programming, Iterations, Optimization