Optimization Online


Looking for strong polynomiality in Linear Programming : Arguments, conjectures, experiments, findings, and conclusion.

Peter A. Bruijs (p.a.bruijs***at***wxs.nl)

Abstract: 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.

Keywords: linear programming - simplex algorithm - ellipsoid method - interior-point methods - gradient methods - computational complexity – strong polynomiality

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: january 6, 2015

Download: [PDF]

Entry Submitted: 01/06/2015
Entry Accepted: 01/06/2015
Entry Last Modified: 01/06/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society