Open problems and recent work
There are several open problems in the theory of linear programming, the solution of which would represent fundamental breakthroughs in mathematics and potentially major advances in our ability to solve large-scale linear programs.
- Does LP admit a strongly polynomial-time algorithm?
- Does LP admit a strongly polynomial algorithm to find a strictly complementary solution?
- Does LP admit a polynomial algorithm in the real number (unit cost) model of computation?
This closely related set of problems has been cited by Stephen Smale as among the 18 greatest unsolved problems of the 21st century. In Smale’s words, the third version of the problem “is the main unsolved problem of linear programming theory.” While algorithms exist to solve linear programming in weakly polynomial time, such as the ellipsoid methods and interior-point techniques, no algorithms have yet been found that allow strongly polynomial-time performance in the number of constraints and the number of variables. The development of such algorithms would be of great theoretical interest, and perhaps allow practical gains in solving large LPs as well.
- Are there pivot rules which lead to polynomial-time Simplex variants?
- Do all polyhedral graphs have polynomially-bounded diameter?
- Is the Hirsch conjecture true for polyhedral graphs?
These questions relate to the performance analysis and development of Simplex-like methods. The immense efficiency of the Simplex algorithm in practice despite its exponential-time theoretical performance hints that there may be variations of Simplex that run in polynomial or even strongly polynomial time. It would be of great practical and theoretical significance to know whether any such variants exist, particularly as an approach to deciding if LP can be solved in strongly polynomial time.
The Simplex algorithm and its variants fall in the family of edge-following algorithms, so named because they solve linear programming problems by moving from vertex to vertex along edges of a polyhedron. This means that their theoretical performance is limited by the maximum number of edges between any two vertices on the LP polyhedron. As a result, we are interested in knowing the maximum graph-theoretical diameter of polyhedral graphs. It has been proved that all polyhedra have subexponential diameter, and all experimentally observed polyhedra have linear diameter, it is presently unknown whether any polyhedron has superpolynomial or even superlinear diameter. If any such polyhedra exist, then no edge-following variant can run in polynomial or linear time, respectively. Questions about polyhedron diameter are of independent mathematical interest.
Simplex pivot methods preserve primal (or dual) feasibility. On the other hand, criss-cross pivot methods do not preserve (primal or dual) feasibility — they may visit primal feasible, dual feasible or primal-and-dual infeasible bases in any order. Pivot methods of this type have been studied since the 1970s. Essentially, these methods attempt to find the shortest pivot path on the arrangement polytope under the linear programming problem. In contrast to polyhedral graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomial-time criss-cross pivot algorithm without resolving questions about the diameter of general polyhedra.