Linear Programming AlgorithmsBases, Feasibility, and Local OptimalityThe Primal Simplex Algorithm: Falling MarblesThe Dual Simplex Algorithm: Rising BubblesComputing the Initial BasisLinear Expected Time for Fixed DimensionsAlgorithms Lecture 17: Linear Programming AlgorithmsUt ait ille tragicus, ‘veritatis simplex oratio est’, ideoque illam implicarinon oportet. [As the tragic poet says, ‘The language of truth is simple’;therefore it is improper to be entangled by it.]— Seneca the Younger (quoting Euripides)Epistularum Moralium Ad Lucilio, (c. 60 AD)Simplicibus itaque verbis gaudet Mathematica Veritas, cum etiam per sesimplex sit Veritatis oratio. [And thus Mathematical Truth prefers simplewords, because the language of Truth is itself simple.]— Tycho Brahe (quoting Seneca)Epistolarum astronomicarum liber primus (1596)When a jar is broken, the space that was insideMerges into the space outside.In the same way, my mind has merged in God;To me, there appears no duality.— Sankara, Viveka-Chudamani (c. 700), translator unknown17 Linear Programming AlgorithmsIn this lecture, we’ll see a few algorithms for actually solving linear programming problems. Themost famous of these, the simplex method, was proposed by George Dantzig in 1947. Althoughmost variants of the simplex algorithm performs well in practice, there is no sub-exponential upperbound on the running time of any simplex variant. However, if the dimension of the problem isconsidered a constant, there are several linear programming algorithms that run in linear time. I’lldescribe a particularly simple randomized algorithm due to Raimund Seidel.My approach to describing these algorithms will rely much more heavily on geometric intu-ition than the usual linear-algebraic formalism. This works better for me, but your mileage mayvary. For a more traditional description of the simplex algorithm, see Robert Vanderbei’s excellenttextbook Linear Programming: Foundations and Extensions [Springer, 2001], which can be freelydownloaded (but not legally printed) from the author’s website.17.1 Bases, Feasibility, and Local OptimalityConsider the canonical linear program max{c · x | Ax ≤ b, x ≥ 0}, where A is an n × d constraintmatrix, b is an n-dimensional coefficient vector, and c is a d-dimensional objective vector. We willinterpret this linear program geometrically as looking for the lowest point in a convex polyhedronin IRd, described as the intersection of n + d halfspaces. As in the last lecture, we will consideronly non-degenerate linear programs: Every subset of d constraint hyperplanes intersects in a singlepoint; at most d constraint hyperplanes pass through any point; and objective vector is linearlyindependent from any d − 1 constraint vectors.A basis is a subset of d constraints, which by our non-degeneracy assumption must be linearlyindependent. The location of a basis is the unique point x that satisfies all d constraints withequality; geometrically, x is the unique intersection point of the d hyperplanes. The value of abasis is c · x, where x is the location of the basis. There are preciselyn+ddbases. Geometrically,the set of constraint hyperplanes defines a decomposition of IRdinto convex polyhedra; this celldecomposition is called the arrangement of the hyperplanes. Every subset of d hyperplanes (i.e.,every basis) defines a vertex of this arrangement (the location of the basis). I will use the words‘vertex’ and ‘basis’ interchangeably.1Algorithms Lecture 17: Linear Programming AlgorithmsA basis is feasible if its location x satisfies all the linear constraints, or geometrically, if thepoint x is a vertex of the polyhedron. If there are no feasible bases, the linear program is infeasible.A basis is locally optimal if its location x is the optimal solution to the linear program withthe same objective function and only the constraints in the basis. Geometrically, a basis is locallyoptimal if its location x is the lowest point in the intersection of those d halfspaces. A careful readingof the proof of the Strong Duality Theorem reveals that local optimality is the dual equivalent offeasibility; a basis is locally feasible for a linear program Π if and only if the same basis is feasiblefor the dual linear program q. For this reason, locally optimal bases are sometimes also called dualfeasible. If there are no locally optimal bases, the linear program is unbounded.1Two bases are neighbors if they have d − 1 constraints in common. Equivalently, in geometricterms, two vertices are neighbors if they lie on a line determined by some d − 1 constraint hy-perplanes. Every basis is a neighbor of exactly dn other bases; to change a basis into one of itsneighbors, there are d choices for which constraint to remove and n choices for which constraint toadd. The graph of vertices and edges on the boundary of the feasible polyhedron is a subgraph ofthe basis graph.The Weak Duality Theorem implies that the value of every feasible basis is less than or equalto the value of every locally optimal basis; equivalently, every feasible vertex is higher than ev-ery locally optimal vertex. The Strong Duality Theorem implies that (under our non-degeneracyassumption), if a linear program has an optimal solution, it is the unique vertex that is both feasi-ble and locally optimal. Moreover, the optimal solution is both the lowest feasible vertex and thehighest locally optimal vertex.17.2 The Primal Simplex Algorithm: Falling MarblesFrom a geometric standpoint, Dantzig’s simplex algorithm is very simple. The input is a set ofhalfspaces H; we want the lowest vertex in the intersection of these halfspaces.SIMPLEX1(H):if ∩ H = ∅return INFEASIBLEx ← any feasible vertexwhile x is not locally optimalhhpivot downward, maintaining feasibility iiif every feasible neighbor of x is higher than xreturn UNBOUNDEDelsex ← any feasible neighbor of x that is lower than xreturn xLet’s ignore the first three lines for the moment. The algorithm maintains a feasible vertex x.At each so-called pivot operation, the algorithm moves to a lower vertex, so the algorithm nevervisits the same vertex more than once. Thus, the algorithm must halt after at mostn+ddpivots.When the algorithm halts, either the feasible vertex x is locally optimal, and therefore the optimumvertex, or the feasible vertex x is not locally optimal but has no lower feasible neighbor, in whichcase the feasible region must be unbounded.1For