Linear Programming and Simplex Algorithm Insights

Randomized pivoting rules for the simplex algorithm upper and lower bounds Uri Zwick ( ) Tel Aviv University AAAC 2018 Asian Association for Algorithms and Computation May 19, 2018

Linear Programming max ??? s.t. ?? ? Maximize a linear objective function subject to a set of linear inequalities (and equalities) Find the highest point in a polyhedron

The Simplex Algorithm [Dantzig (1947)] Start at some vertex. Move up, from vertex to vertex, along edges, until reaching the top.

Pivoting rules Which up-going edge to take? ? The top will always be reached, but after how many steps?

Deterministic pivoting rules Largest improvement Largest slope Dantzig s rule Largest modified cost Bland s rule (avoids cycling) Lexicographic rule (also avoids cycling) Zadeh s rule least recently entered All known deterministic pivoting rules require an exponential number of steps, in the worst-case [Klee-Minty (1972)] , , [Amenta-Ziegler (1996)] [Friedmann (2011)]

Algorithms for Linear Programming Simplex[Dantzig 1947] No polynomial version known (yet?) Ellipsoid [Khachiyan (1979)] Interior-point [Karmakar (1984)] Smoothed analysis based [Spielman-Teng (2004), Kelner-Spielman (2006)] Polynomial, but not strongly polynomial Not combinatorial

Is the simplex algorithm still interesting? The simplex algorithm works very well in practice. Fundamental and intriguing open problems: 1. Is there a polynomial pivoting rule? 2. Is the diameter polynomial? Is Linear Programming strongly polynomial? 3. Simplex-like algorithms can be used to solve more than just LP problems.

Turn-based 2-Player 0-Sum Stochastic Games [Shapley 53] [Gillette 57] [Condon 92] States are divided between two players, max and min. From each state, there is a collection of available probabilistic actions, each with an associated reward. Players try to maximize/minimize total expected reward. Both players have optimal positional strategies Can optimal strategies be found in polynomial time? Best known algorithm is a sub-exponential simplex-like algorithm

Markov Decision Processes [Shapley 53] [Bellman 57] [Howard 60] When there is only one player, the game is known as a Markov Decision Process. The game ends when the token reaches the sink. Optimal positional strategies can be found using LP Is there a strongly polynomial time algorithm?

Diameter of polytopes Hirsch Conjecture (1957) The diameter of a ?-dimensional, ?-faceted polytope is at most ? ? Refuted! [Santos (2010)] Diameter is still believed to be polynomial Quasi-polynomial upper bound [Kalai-Kleitman (1992)] ([Todd (2014)])

Vertices, edges and facets ?T? = ? Polytope in ? ? dimension Supporting hyperplane: Polytope is on one side. Non-empty intersection. ?-face: ? ?-dimensional intersection of the polytope with a supporting hyperplane. 0-face Vertex

Vertices, edges and facets Polytope in ? ? dimension Supporting hyperplane: Polytope is on one side. Non-empty intersection. ?-face: ? ?-dimensional intersection of the polytope with a supporting hyperplane. 1-face Edge 0-face Vertex

Vertices, edges and facets Polytope in ? ? dimension Supporting hyperplane: Polytope is on one side. Non-empty intersection. ?-face: ? ?-dimensional intersection of the polytope with a supporting hyperplane. 1-face Edge 0-face Vertex (? 1)-face Facet

Randomized pivoting rules Random-Edge Choose a random improving edge [Dantzig (1947)] Random-Facet [Kalai (1992)] [Matou ek-Sharir-Welzl (1992)] To be described shortly Random-Facet is sub-exponential!

Primal Random-Facet [Kalai (1992)] Choose at random one of the ? facets containing the current vertex. Recursively find the top vertex on the chosen facet. (The chosen facet inequality becomes an equality.) (A (? 1)-dimensional sub-problem.) If vertex reached is the top vertex of the whole polyhedron, we are done. Otherwise, do a pivoting step out of the facet and continue recursively from the vertex reached.

Inactive Inactive facet - All vertices on the facet are below the current vertex.

Inactive Inactive

Primal Random-Facet [Kalai (1992)] Order the ? facets containing the current vertex according to the height of the top vertex on them. If the algorithm chooses the ?-th facet, then (at least) ? facets become inactive. ? ? ?,? = ? ? 1,? 1 + 1 +1 ? ?=1 ?(?,? ?) ? ?,? = e2 ? ? ln ? Note: ? here is the number of active facets, which is not known to the algorithm.

Unusual recurrence relations Unusual 2D recurrence relations are much harder to analyze, but exhibit similar behavior.

Linear Programming Duality ? variables ? inequalities ? variables ? inequalities ? equalities ? ? free variables ? inequalities

Linear Programming Duality d variables n inequalities ? ? free variables ? inequalities ? 2? Faster when

Dual Random-Facet [Matou ek-Sharir-Welzl (1992)] Choose a random facet not containing the current (infeasible) basic solution (bs). Solve recursively without this facet, starting from the current basic solution. If the bs obtained is on the right side of the ignored facet, i.e., is a vertex, we are done. Otherwise, do a dual pivoting step to a basic solution on the ignored facet and recurse.

Improved Random-Facet [Kalai (1992) (1996)] [G rtner (1995)] [Hansen-Z (2014)] Improved Random-Facet is (almost) a primal algorithm. It is faster than both Primal and Dual Random-Facet. When ? = ?(?), both Primal and Dual Random-Facet run in ? 2? log ? time, while Improved runs in ? 2? time. Improved either follows an edge to an adjacent vertex, or jumps back to a previously visited vertex. Improved Random-Facet defines a tree, rather than a path.

Acyclic Unique Sink Orientations (AUSOs) Acyclic orientation of the edges of a polytope such that every face has a unique sink A linear objective function gives rise to an AUSO. Most AUSOs do not correspond to LPs.

Random-Facet on AUSOs The analysis of Random-Facet only uses the AUSO properties. Thus, the 2 ? but also any problem that defines an AUSO. ? upper bound holds not just for LPs, The 2-player stochastic games define AUSOs. Thus, they can be solved using Random-Facet. [Matousek (1994)] showed that the analysis of Random-Facet is tight for AUSOs of the ?-cube. Does Random-Facet run faster on LPs? Random-Facet is not polynomial, even for LPs.

(Sub-)Exponential lower bounds Random Edge and Random Facet [Friedmann-Hansen-Z (2011,2014)] Random-Edge and Random-Facet are not polynomial even on LPs. Lower bound for Random-Edge obtained on an LP corresponding to a Markov Decision Process (MDP) Lower bound for Random-Facet obtained on an LP corresponding to a Shortest Path problem.

Decision node 3-bit counter payoff ( N)15 Token Randomization node

3-bit counter 0 1 0

3-bit counter Improving switches Random-Edge can choose either one of these improving switches 0 1 0

Cycle gadgets Cycles close one edge at a time Shorter cycles close faster

Cycle gadgets Cycles open simultaneously

3-bit counter 23 0 1 0 1

3-bit counter 34 1 0 1

Size of cycles Various cycles and lanes compete with each other Some are trying to open while some are trying to close We need to make sure that our candidates win! Length of all A-cycles = 8? Length of all C-cycles = 22? Length of Bi-cycle = 25?2? ?(?4)vertices for an ?-bit counter 2 ?1/4 lower bound Can be improved using a more complicated construction and an improved analysis (work in progress)

Randomized Pivoting Rules Upper and lower bounds Algorithm RANDOM EDGE RANDOM FACET Lower bound 2 ? ?1/4 Upper bound ??? 2 ? ?1/3 2 ? ? [Kalai 92] [Matousek-Sharir-Welzl 92] [Friedmann-Hansen-Z (2011,2014)]

AUSOs of the ?-cube Algorithm RANDOM EDGE RANDOM FACET Lower bound Upper bound 1.8? 2 ? log ? 2 ? 2? ? [Hansen-Paterson-Z (2014)] [Hansen-Z (2016)] [G rtner (2002)] [Matousek (1994)]

AUSOs of the ?-cube Algorithm RANDOM EDGE RANDOM FACET Lower bound Upper bound 1.8? 2 ? log ? 2 ? 2? ? Random-Edge is slower than Random-Facet ! (on AUSOs of the ?-cube)

Concluding remarks and open problems Is there a polynomial pivoting rule? Is the diameter polynomial? Is Linear Programming strongly polynomial? Are there better randomized pivoting rules? Is Random-Edge subexponential? Subexponential lower bound for Improved-Random-Facet? Are there deterministic subexponential pivoting rules? Faster algorithms for Turn-based 2-Player 0-Sum Stochastic Games?