Optimization Methods The Simplex Method II

Optimization Methods The Simplex Method 1 Outline Slide 1 Revised Simplex method The full tableau implementation Finding an initial BFS The complete algorithm The column geometry Computational e ciency 2 Revised Simplex Initial data: A b c 1. Start with basis B = AB(1) : : : AB(m) ] and B ;1. 2. Compute p0 = c0B B ;1 cj = cj ; p0 Aj If cj  0 x optimal stop. Else select j : cj < 0. 3. Compute u = B ;1Aj . If u  0 ) cost unbounded stop Else xB(i) uB(l) = u 4. � = 1�i�min m u >0 u i i Slide 2 Slide 3 l 5. Form a new basis B by replacing AB(l) with Aj . 6. yj = � , yB(i) = xB(i) ; � ui 7. Form B ;1ju] 8. Add to each one of its rows a multiple of the lth row in order to make the last column equal to the unit vector el . The rst m columns is B ;1. 1 Slide 4 2.1 Example min x1+ 5x2 s:t: x1+ x2+ x1 Slide 5 ;2x3 x3 4 2 3 6 0 x3 3x2+ x3 x1 x2 x3 BFS: x = (2 0 2 0 0 1 4)0 B = fA1 A3 A6 A7 g, c0 = (20 7 0 2 ;3 030) 2 1 1 0 0 0 1 6 7 6 1 0 0 0 B = 64 0 1 1 0 75 B;1 = 64 ;11 ;11 0 1 0 1 ;1 1 (u1 u3 u6; u7)0 =B ;1A5 = (1 ;1 1 1)0 � = min 12 11 14 = 1, l = 6 l = 6 (A6 exits 2 the basis). 3 0 1 0 0 1 6 7 B ;1ju] = 64 ;11 ;11 01 00 ;11 75 2 ;1 1 0 1 3 1 1 0 ;1 0 ;1 6 0 0 1 07 )B =6 4 ;1 1 1 0 7 5 0 0 ;1 1 0 0 1 0 Slide 6 3 0 0 77 05 1 Slide 7 2.2 Practical issues Slide 8 Numerical Stability ; B needs to be computed from scratch once in a while, as errors accu1 mulate Sparsity ; B is represented in terms of sparse triangular matrices 1 3 Full tableau implementation c B; b c0 ; c0B B; A B; b B; A ; 0B 1 1 1 1 or, in more detail, 2 Slide 9 c x ; 0B B xB(1) .. . xB(m) 3.1 Example min s:t: c1 ::: j cn j B; A : : : B; An 1 1 1 j j 12x2 ; 12x3 x1 + 2x2 + 2x3  20 2x1 + x2 + 2x3  20 2x1 + 2x2 + x3  20 x1 x2 x3  0 min ;10x1 ; 12x2 ; 12x3 s:t: x1 + 2x2 + 2x3 + x4 = 20 + x5 = 20 2x1 + x2 + 2x3 2x1 + 2x2 + x3 + x6 = 20 x1 : : : x6  0 BFS: x = (0 0 0 20 20 20)0 B=A4 A5 A6 ] 0 x4 = 20 x5 = 20 x6 = 20 ;10x1 ; x1 ;10 1 2* 2 x2 ;12 2 1 2 Slide 12 1 x 1 x 2 x 3 x4 0 ;7 ;2 0 0 1.5 1* 1 1 0.5 1 0 0 1 ;1 0 3 Slide 11 x3 x4 x5 x6 ;12 0 0 0 2 1 0 0 2 0 1 0 1 0 0 1 c0 = c0 ; cB0 B; A = c0 = (;10 ;12 ;12 0 0 0) 100 x4 = 10 x1 = 10 x6 = 0 Slide 10 x5 x6 5 0 ;0.5 0 0.5 0 ;1 1 Slide 13 x 1 x 2 x 3 x4 0 ;4 0 2 0 1.5 1 1 1 ;1 0 ;1 0 2.5* 0 1 120 x3 = 10 x1 = 0 x6 = 10 x1 x2 x3 0 0 0 0 0 1 1 0 0 0 1 0 136 x3 = 4 x1 = 4 x2 = 4 x5 x6 4 0 ;0.5 0 1 0 ;1:5 1 x4 3.6 0.4 ;0.6 0.4 x5 1.6 0.4 0.4 ;0.6 x6 1.6 ;0.6 0.4 0.4 Slide 14 Slide 15 x3 . B = (0,0,10) . E = (4,4,4) A = (0,0,0) . . . C = (0,10,0) D = (10,0,0) x2 x1 4 Comparison of implementations Memory Worst-case time Best-case time Full tableau Revised simplex O(mn) O(mn) O(mn) 4 O(m2 ) O(mn) O(m2 ) Slide 16 5 Finding an initial BFS Goal: Obtain a BFS of Ax = b x  0 Slide 17 or decide that LOP is infeasible. Special case: b  0 Ax  b x  0 ) Ax + s = b x s  0 s=b x=0 5.1 Articial variables Ax = b x  0 1. Multiply rows with ;1 to get b � 0. 2. Introduce articial variables y, start with initial BFS y = b x = 0, and Slide 18 apply simplex to auxiliary problem min y1 + y2 + : : : + ym s:t: Ax + y = b x y�0 3. If cost > 0 ) LOP infeasible stop. Slide 19 4. If cost = 0 and no articial variable is in the basis, then a BFS was found. 5. Else, all yi� = 0, but some are still in the basis. Say we have AB(1) : : : AB(k) in basis k < m. There are m ; k additional columns of A to form a basis. Slide 20 6. Drive articial variables out of the basis: If lth basic variable is articial examine lth row of B ;1A. If all elements = 0 ) row redundant. Otherwise pivot with 6= 0 element. 6 A complete Algorithm for LO Phase I: Slide 21 1. By multiplying some of the constraints by ;1, change the problem so that b  0. P 2. Introduce y1 : : : ym , if necessary, and apply the simplex method to min mi�1 yi . 3. If cost> 0, original problem is infeasible STOP. 5 4. If cost= 0, a feasible solution to the original problem has been found. 5. Drive articial variables out of the basis, potentially eliminating redundant rows. Phase II: Slide 22 1. Let the nal basis and tableau obtained from Phase I be the initial basis and tableau for Phase II. 2. Compute the reduced costs of all variables for this initial basis, using the cost coe cients of the original problem. 3. Apply the simplex method to the original problem. 6.1 Possible outcomes 1. Infeasible: Detected at Phase I. 2. A has linearly dependent rows: Detected at Phase I, eliminate redundant rows. 3. Unbounded (cost= ;1): detected at Phase II. 4. Optimal solution: Terminate at Phase II in optimality check. 7 The big-M method min n X j �1 cj xj + M s:t: Ax + y = b m X i�1 yi Slide 23 Slide 24 x y0 8 The Column Geometry min c0x s:t: Ax = b e0x = 1 1 1 1  x0   A A A n x c + x c +    + xn cn = bz  2 Slide 25 2 2 6 Slide 26 Slide 27 z B . . . I H F G C D E b . initial basis . z . . 3 4 6 . . . . . . 2 1 7 next basis 8 5 optimal basis b 7 9 Computational e ciency Slide 28 Exceptional practical behavior: linear in n Worst case max xn s:t:   x1  1 xi;1  xi  1 ; xi;1 i = 2 ::: n Slide 29 x3 x2 x2 x1 x1 (b) (a) Theorem The feasible set has 2n vertices The vertices can be ordered so that each one is adjacent to and has lower cost than the previous one. There exists a pivoting rule under which the simplex method requires 2n ; 1 changes of basis before it terminates. 8 Slide 30