MthSc-440/640: Linear ProgrammingLecture 15Pietro BelottiDept. of Mathematical SciencesClemson UniversityOctober 14, 2010Reading for Today: pages 97-105.Reading for Tuesday: pages 105-113.Homework #4 out after class. Due Thursday, October 21.Recap: the simplex m ethod◮Reduce problem to standard form◮Add slack variables◮Get initial dictionary◮If infeasible, do Phase I◮If no feasible solution, STOP – problem infeasible◮Repeat pivoting until◮unbounded◮optimumRecap: all possible situations◮Degeneracy: the objective doesn’t improve; keep pivoting.◮Cycling: very rare – apply Bland’s rule.◮Infeasibility: apply Phase I◮If, at optimum of Phase I, x0> 0 ⇒ infeasible◮Otherwise, we have a feasible dictionary.◮Unboundedness: at le ast one candid ate for enteri ng1hasonly non-negative coefficients in the remaining rows of thedictionary.1i.e., its coefficient in the obj. row of the dictionary is > 0.Recap: complexity of the sim plex method◮The Klee-Minty example, with n variables and nconstraints, can be solved in 2n− 1 pivoting operations.⇒ The simplex method is an exponential algorithm;◮the Ellipsoid method is a polynomial algorithm;⇒ Linear Programming is a polynomial problem.◮In theory, the ellipsoid method should be preferred;◮however, (good) implementations of the simplex methodare used in practice.Dictionaries and LPsConsider the LP problem in standard form:max 5x1+ 4x2+ 3x3s.t. 2x1+ 3x2+ x3≤ 54x1+ x2+ 2x3≤ 113x1+ 4x2+ 2x3≤ 8x1, x2, x3≥ 0,and rewrite it with equality constraints:max 5x1+ 4x2+ 3x3s.t. 2x1+ 3x2+ x3+ x4= 54x1+ x2+ 2x3+ x5= 113x1+ 4x2+ 2x3+ x6= 8x1, x2, x3, x4, x5, x6≥ 0.Dictionaries and LPsA dictionary is simply another way to express the LP:max 5x1+ 4x2+ 3x3s.t.x4= 5 − 2x1− 3x2− x3x5= 11 − 4x1− x2− 2x3x6= 8 − 3x1− 4x2− 2x3x1, x2, x3, x4, x5, x6≥ 0in many2equivalent ways—this is the second dictionary:max252−72x2+12x3−52x4s.t.x1=52−32x2−12x3−12x4x5= 1 + 5x2+ 2x4x6=12+12x2−12x3+32x4x1, x2, x3, x4, x5, x6≥ 0.2To be precise,!m+nm=!3+33= 20 ways.Bases and dict ionariesConsider now an LP with n + m variables, m constraints:max c⊤xs.t. Ax = bx ≥ 0Consider index sets B and N , both subsets of {1, 2 . . . , n + m}and such that B ∪ N = {1, 2 . . . , n + m}.A = [B N], where B and N are m × m and m × n submatrices ofA, respectively, and are defined by index sets B, N .Similarly, c = (cBcN) and x = ( xBxN). Thenmax c⊤BxB+ c⊤NxNs.t. BxB+ NxN= bxB, xN≥ 0.Bases and dict ionariesSuppose B is nonsingular, therefore invertible.Multiply both sides by B−1:BxB+ NxN= b ⇐⇒ xB= B−1b − B−1NxN.As for the objective function,c⊤BxB+ c⊤NxN=c⊤B(B−1b − B−1NxN) + c⊤NxNc⊤BB−1b + (c⊤N− c⊤BB−1N)xNBases and dict ionariesThus a dictionary in matricial form isxB= B−1b − B−1NxNz = c⊤BB−1b + (c⊤N− c⊤BB−1N)xNBy setting the nonbasic variables xNto zero, we obtain:◮The solution B⊤b (feasible if B⊤b ≥ 0);◮The objective function value c⊤BB−1b;◮The vector c⊤N− c⊤BB−1N to check for optimality: if at leastone component is positive, the solution is not optimal.Let’s rewrite the dictionary asxB=¯b −¯NxNz = c⊤B¯b +¯c⊤NxNComplexity of a single iterationxB=¯b −¯NxNz = c⊤B¯b +¯c⊤NxNAn iteration (pivoting) is:◮If¯cN≤ 0, stop: optimum, value: c⊤B¯b;◮Otherwise, select i ∈ N such that (¯cN)i> 0;◮Consider the corresponding column¯Niof¯N;◮Determine j ∈ B such that j = argminj∈B:¯Nij>0¯bj¯Nij◮i enters the basis, j leaves:◮B ← B ∪ {i} \ {j}◮N ← N ∪ {j} \ {i}PivotingThe way we did it in class, we’d rewrite the equation of xjisolating xi(¯Njis the corresponding row)xBj=¯bj−¯N⊤jxN⇒ xNi=1Nij¯bj− xBj−Xk∈N \{i}¯NijxNkand sub xiin the remaining m rows (m − 1 plus the obj. row).For a problem in standard form with m constraints and nvariables, each operation has a complexity of O(mn).However, to get a new basis B′, all we need is:◮select i with positive (¯cn)i, if any → entering variable◮look at Nito find argminj∈B:¯Nij>0¯bj¯Nij→ leaving variableThe revised sim plex methodFind initial basis B, then◮Compute¯c⊤N= c⊤N− c⊤BB−1N to find positive components◮Find leaving variable◮RepeatTo compute¯cB= c⊤N− c⊤BB−1N and¯N = B−1N, find first c⊤BB−1.(⋆) Don’t invert B. Find vector y such that y⊤B = c⊤B.◮This is a system of m equations in m unknowns.(⋆⋆) Then, compute c⊤N− y⊤N. Choose entering i (if any).◮i corresponds to a column of N, let’s call it a.◮In the current dictionary, the i-th column is B−1a.◮Compute B−1a by solving Bd = a.◮Select exiting variable j: find min t such that xB− td = 0.◮B ← B ∪ {i} \ {j}. Repeat.What’s new?◮We won’t miss recomputing the whole dictionary◮However, we need to solve two m × m systems of linearequations at every iteration of the RSM◮Every system is only slightly different from the previous◮(B differs in two out of m elements)Q. Can we exploit this?A. We’ll see this next time.Revised simplex an d the dual problemFor any B, if the primal is:max c⊤BxB+ c⊤NxNs.t. BxB+ NxN= bxB, xN≥ 0,then the dual is (let’s denote dual variables as y):min y⊤bs.t. y⊤B ≥ cBy⊤N ≥ cN.Revised simplex an d complementar y slacknessHow do we check if B is an optimal basis?Suppose B is nondegenerate. By complementary slackness:◮xBnonzero ⇒ their dual constraints hold at equality.◮xNare zero ⇒ nothing is required.min y⊤bs.t. y⊤B ≥ cB(xB)y⊤N ≥ cN(xN).Complementary slackness ⇒ y⊤B = cBDual feasibility ⇒ y⊤N ≥ cNThose are precisely the tests done at (⋆) and (⋆⋆) .