Yinyu Ye MS E Stanford MS E310 Lecture Note 07 More Simplex Pivoting Rules and Sensitivity Analyses Yinyu Ye Department of Management Science and Engineering Stanford University Stanford CA 94305 U S A http www stanford edu yyye LY Chapter 3 Homework and 5 2 1 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 How Good is the Greedy Pivoting Rule Very good on average but the worse case When the simplex method is used to solve a linear program the number of iterations to solve the problem starting from a basic feasible solution is typically a small multiple of m e g between 2m and 3m At one time researchers believed and attempted to prove that the simplex algorithm or some variant thereof always requires a number of iterations that is bounded by a polynomial expression in the problem size 2 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 Klee and Minty Example Consider max xn subject to x1 0 x1 1 where 0 xj xj 1 j 2 n xj 1 xj 1 j 2 n 1 2 This presentation of the problem emphasizes the idea see the figures below that the feasible region of the problem is a perturbation of the n cube 3 Yinyu Ye MS E Stanford In the case of n above looks like MS E310 Lecture Note 07 2 and 1 4 the feasible region of the linear program x2 1 x1 1 4 Yinyu Ye MS E Stanford For the case where n MS E310 Lecture Note 07 3 the feasible region of the problem above looks like x3 1 x 2 x1 1 5 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 The formulation above does not immediately reveal the standard form representation of the problem Instead we consider a different one namely n max subject to 2 i 1 10n j xj j 1 10i j xj xi 100i 1 i 1 n 0 j 1 n j 1 xj The problem above a also be used is easily cast as a linear program in standard form Unfortunately it is less apparent how to exhibit the relationship between its feasible region and a perturbation of the unit cube a It should be noted that there is no need to express this problem in terms of powers of 10 Using any constant C 1 would yield the same effect an exponential number of pivot steps 6 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 7 Example max subject to 100x1 10x2 x3 x1 20x1 x2 200x1 20x2 x3 1 100 10 000 In this case we have three constraints and three variables along with their non negativity constraints After adding slack variables we get a problem in standard form The system has m 3 equations and n 6 nonnegative variables In tableau form the problem is Yinyu Ye MS E Stanford 0 T MS E310 Lecture Note 07 8 z x1 x2 x3 x4 x5 x6 1 1 100 10 1 0 0 0 0 0 1 0 0 1 0 0 1 0 20 1 0 0 1 0 100 0 200 20 1 0 0 1 10 000 The bullets below the tableau indicate the columns that are basic Yinyu Ye MS E Stanford 1 T MS E310 Lecture Note 07 z x1 x2 x3 x4 1 0 10 1 0 1 0 0 0 0 0 9 x5 x6 1 100 0 0 100 0 1 0 0 1 1 0 20 1 0 80 20 1 200 0 1 9 800 Yinyu Ye MS E Stanford 2 T MS E310 Lecture Note 07 10 z x1 x2 x3 x4 x5 x6 1 1 0 0 1 100 10 0 900 0 1 0 0 1 0 0 1 0 0 1 0 20 1 0 80 0 0 0 1 200 20 1 8 200 Yinyu Ye MS E Stanford z 3 T MS E310 Lecture Note 07 11 x1 x2 x3 x4 x5 x6 1 1 100 0 1 0 10 0 1 000 0 1 0 0 1 0 0 1 0 20 1 0 0 1 0 100 0 200 0 1 0 20 1 8 000 Yinyu Ye MS E Stanford z 4 T MS E310 Lecture Note 07 12 x1 x2 x3 x4 x5 x6 1 1 100 0 0 0 10 1 9 000 0 1 0 0 1 0 0 1 0 20 1 0 0 1 0 100 0 200 0 1 0 20 1 8 000 Yinyu Ye MS E Stanford 5 T MS E310 Lecture Note 07 13 z x1 x2 x3 x4 x5 x6 1 1 0 0 0 100 10 1 9 100 0 1 0 0 1 0 0 1 0 0 1 0 20 1 0 80 0 0 0 1 200 20 1 8 200 Yinyu Ye MS E Stanford 6 T MS E310 Lecture Note 07 z x1 x2 x3 x4 1 0 10 0 0 1 0 0 0 0 0 14 x5 x6 1 100 0 1 9 900 0 1 0 0 1 1 0 20 1 0 80 20 1 200 0 1 9 800 Yinyu Ye MS E Stanford z 7 T MS E310 Lecture Note 07 15 x1 x2 x3 x4 x5 x6 1 1 100 10 0 0 0 1 10 000 0 1 0 0 1 0 0 1 0 20 1 0 0 1 0 100 0 200 20 1 0 0 1 10 000 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 x1 x2 x3 x4 x5 x6 0 0 104 1 102 0 is optimal and that the objective function value is 10 000 Along the way we made 2 3 1 7 pivot steps The objective function made a strict increase with each change of basis Remark The instance of the linear program 1 in which n 3 leads to 2 3 1 pivot steps when the greedy rule is used to select the pivot column The general problem of the class 1 takes 2 n 1 pivot steps To get an idea of how bad this can be consider the case where n 50 Now 2 50 1 1015 In a year with 365 days there are approximately 3 10 7 seconds If a computer were running continuously and performing T iterations of the Simplex Algorithm per second it would take approximately 1 1015 8 10 years 8 3T 10 3T to solve the problem using the Simplex Algorithm with the greedy pivot selection rule 16 Yinyu Ye MS E Stanford MS E310 Lecture Note 07 An interesting connection Consider the eight vectors v k v1k v2k v3k where k 0 1 7 and 1 vjk 0 if xj is basic in tableau k otherwise Looking at the eight tableaus T 0 T1 T7 we see that v 0 0 0 0 v 4 0 1 1 v 1 1 0 0 v 5 1 1 1 v 2 1 1 0 v 6 1 0 1 v 3 0 1 0 v 7 0 0 1 Now …