Until now it has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm with its combinatorial nature does not even offer a polynomial bound, whereas the complexity of the polynomial algorithms by Khachiyan and Karmarkar is based on the number of variables n, and quadratically on the length L of a bit-sequence representing the problem data. The curious fact that non-linear algorithms would be needed to deliver the strongest complexity result for LP has served as the motivation for research producing the findings presented here. In the arguments part this paper identifies characteristics of current LP-algorithms that hinder attaining strong polynomiality. This leads to conjectures concerning possible complexity outcomes on the basis of linear gradient-like algorithms, feasible gradient algorithms, that might offer a (strong) polynomial bound. Experiments based on these algorithms, treating well-known problems from the literature, and a great many random problems have made clear that these algorithms generally do have strong characteristics, but their ultimate complexity depends on the precise implementation chosen. Although an early conjecture of extremely strong polynomiality has been refuted by these experiments, a revised conjecture has not been refuted, but is firmly sustained by ample computational results, and by intuitive and ultimately theoretical arguments.
Citation
january 6, 2015