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

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.