Optimization Methods in Management Science Tutorial 5 - Degeneracy

Degeneracy in Linear Programming Sorry, Tim. But the topic is just as interesting. It’s about degeneracy in Linear Programming. Degeneracy? Students shouldn’t learn about degeneracy. I heard that today’s tutorial is all about Ellen DeGeneres Ellen DeGeneres Tim, the turkey Actually, they studied convex sets. 1 What is degeneracy? • As you know, the simplex algorithm starts at a corner point and moves to an adjacent corner point by increasing the value of a non-basic variable xs with a negative value in the z-row (objective function). • Typically, the entering variable xs does increase in value, and the objective value z improves. But it is possible that that xs does not increase at all. It will happen when one of the RHS coefficients is 0. • In this case, the objective value and solution does not change, but there is an exiting variable. This situation is called degeneracy. z x1 x2 x3 x4 1 3 -2 0 0 = 2 0 -3 3 1 0 = 6 1 = 0 -4 2 0 2 0 A basic feasible solution is called degenerate if one of its RHS coefficients (excluding the objective value) is 0. This bfs is degenerate. 2 No, Nooz**. This tutorial has many more slides. Degeneracy adds complications to the simplex algorithm. And if you understand what occurs under degeneracy, you really understand what is going on with the simplex algorithm. Great. I now know what degeneracy is. Now we can move on to other matters. ** As you know, “No, Nooz” is good news.” Ollie, the computationally wise owl. Nooz, the most trusted name in fox. Professor Orlin apologizes for this bad pun, but feels that he could not resist the temptation. Cleaver 3 Degeneracy and Basic Feasible Solutions • We may think that every two distinct bases lead to two different solutions. This would be true if there was no degeneracy. But with degeneracy, we can have two different bases, and the same feasible solution. z x1 x2 x3 x4 z x1 x2 x3 x4 1 3 -2 0 0 = 2 1 3 2 -2 0 0 0 1 = 2 0 -3 3 1 0 = 6 0 -3 -3/2 3 0 1 0 -3/2 = 6 0 -4 2 0 1 = 2 0 0 -1 -1/2 2 1 0 1 1/2 = 2 0 We now pivot on the “2” in Constraint 2 and obtain a second tableau. Both tableus correspond to the same feasible solution with z = 2, x1 = x2 = x4 = 0; x3 = 6. But the basic variables and the coefficients of the two tableaus are different. 4 z x1 x2 x3 x4 z x1 x2 x3 x4 1 3 -2 0 0 = 2 1 3 2 -2 0 0 0 1 = 2 0 -3 3 1 0 = 6 0 -3 -3/2 3 0 1 0 -3/2 = 6 0 -4 2 0 1 = 2 0 0 -1 -1/2 2 1 0 1 1/2 = 2 0 Not only are the two tableaus different, but the second tableau satisfies the optimality conditions. This means that the bfs is optimal, even though we were not aware that the bfs was optimal when we looked at the first tableau. But this all seems very technical. Is it really important? Tim, the turkey Tim, it turns out to be very important. We can show that the simplex algorithm is finite and guaranteed to be valid when there is no degeneracy. When there is degeneracy, we have to modify the algorithm to guarantee finiteness. Ollie 5 The Finiteness of the Simplex Algorithm when there is no degeneracy Recall that the simplex algorithm tries to increase a non-basic variable xs. If there is no degeneracy, then xs will be positive after the pivot, and the objective value will improve. Recall also that each solution produced by the simplex algorithm is a basic feasible solution with m basic variables, where m is the number of constraints. There are a finite number of ways of choosing the basic variables. (An upper bound is n! / (n-m)! m! , which is the number of ways of selecting m basic variables out of n.) So, the simplex algorithm moves from bfs to bfs. And it never repeats a bfs because the objective is constantly improving. This shows that the simplex method is finite, so long as there is no degeneracy. 6 Cycling • If a sequence of pivots starting from some basic feasible solution ends up at the exact same basic feasible solution, then we refer to this as “cycling.” If the simplex method cycles, it can cycle forever. • Klee and Minty [1972] gave an example in which the simplex algorithm really does cycle. Here is their example, with the pivot elements outlined. z x1 x2 x3 x4 x5 x6 x7 RHS 1 - 3/4 20 - 1/2 6 0 0 0 3 0 1/4 -8 -1 9 1 0 0 0 0 1/2 -12 - 1/2 3 0 1 0 0 0 0 0 1 0 0 0 1 1 z x1 x2 x3 x4 x5 x6 x7 RHS 1 0 -4 -3 1/2 33 3 0 0 3 0 1 -32 -4 36 4 0 0 0 0 0 4 1 1/2 -15 -2 1 0 0 0 0 0 1 0 0 0 1 1 Initial tableau After 1 pivot 7 Cycling Example Continued z x1 x2 x3 x4 x5 x6 x7 RHS 1 0 0 -2 18 1 1 0 3 0 1 0 8 -84 -12 8 0 0 0 0 1 3/8 -3 3/4 - 1/2 1/4 0 0 0 0 0 1 0 0 0 1 1 z x1 x2 x3 x4 x5 x6 x7 RHS 1 1/4 0 0 -3 -2 3 0 3 0 1/8 0 1 -10 1/2 -1 1/2 1 0 0 0 - 3/64 1 0 3/16 1/16 - 1/8 0 0 0 - 1/8 0 0 10 1/2 1 1/2 -1 1 1 z x1 x2 x3 x4 x5 x6 x7 RHS 1 - 1/2 16 0 0 -1 1 0 3 0 -2 1/2 56 1 0 2 -6 0 0 0 - 1/4 5 1/3 0 1 1/3 - 2/3 0 0 0 2 1/2 -56 0 0 -2 6 1 1 After 2 pivots After 3 pivots After 4 pivots 8 Cycling Example Continued z x1 x2 x3 x4 x5 x6 x7 RHS 1 -1 3/4 44 1/2 0 0 -2 0 3 0 -1 1/4 28 1/2 0 1 -3 0 0 0 1/6 -4 - 1/6 1 0 1/3 0 0 0 0 0 1 0 0 0 1 1 z x1 x2 x3 x4 x5 x6 x7 RHS 1 - 3/4 20 - 1/2 6 0 0 0 3 0 1/4 -8 -1 9 1 0 0 0 0 1/2 -12 - 1/2 3 0 1 0 0 0 0 0 1 0 0 0 1 1 After 5 pivots After 6 pivots And Klee and Minty said “The first shall be last and the last shall be first”, and they saw that their example of cycling was good. Cleaver 9 Is the simplex method finite? We just proved that the simplex method is finite if there is no degeneracy. But how do we know that the simplex method will terminate if there is degeneracy? Tim, the turkey Tim, there are several approaches to guaranteeing that the simplex method will be finite, including one developed by Professors Magnanti and Orlin. We’ll show the standard approach to guaranteeing finiteness, called the perturbation approach. Ollie 10 The Perturbation Approach • In the perturbation approach, we change the RHS by just a little. If the vector of right hand sides is b1, …, bm, we replace it by d1, …, dm, where dj is very close to bj. We want two properties to hold: 1. No basis is degenerate for the perturbed problem. 2. Any basis that is feasible for the perturbed problem is also feasible for the original problem. It turns out that if (1) and (2) are true, than an optimal basis for the perturbed problem will be optimal for the original problem. Before the perturbation. After the perturbation. z x1 x2 x3 x4 z x1 x2 x3 x4 1 3 -2 0 0 = 2 1 3 -2 0 0 = 2 0 -3 3 1 0 = 6 0 -3 3 1 0 = 6+ε1 0 -4 2 0 1 = 2 0 0 -4 2 0 1 = 22 ε0 11 More on Perturbations I get it. So, we may let ε = .001. Actually, the perturbations are absurdly small. For example, for a 100 variable problem, we may replace, bj by bj + 2-10,000j. Nobody does these perturbations in practice; it would be very impractical. It was developed to guarantee that the simplex method would be finite. And for this purpose they work great! Nooz, the most trusted name in fox. Ollie 12 Degeneracy and the Simplex Algorithm The simplex method without degeneracy The simplex method with degeneracy The solution changes after each pivot. The objective value strictly improves after a pivot. The solution may stay the same after a pivot. The objective value may stay the same. The simplex method is guaranteed to be finite. The simplex method may cycle and be infinite. But it becomes finite if we use the perturbation approach or several other approaches. Two different tableaus in canonical form give two different solutions. It is possible that there are two different sets of basic variables that give the same solution. 13 Degeneracy vs. Alternative Optima Finally, degeneracy is similar to but different from the condition for alternate optima. In degeneracy, one of the RHS values is 0. For alternate optima, in an optimal tableau one of the non-basic z-row coefficients is 0. z x1 x2 x3 x4 1 0 4 0 0 = 8 0 1 3 1 0 = 6 0 -1 2 0 1 = 2 The optimal solution is: z = 8, x1 = x2 = 0, x3 = 6, and x4 = 8. x1 is nonbasic, and its z-row coefficient is 0. Increasing x1 (and adjusting x3 and x4) does not change z, and so the solution value remains optimal. Ollie 14 Summary • Degeneracy is important because we want the simplex method to be finite, and the generic simplex method is not finite if bases are permitted to be degenerate. • In principle, cycling can occur if there is degeneracy. In practice, cycling does not arise, but no one really knows why not. Perhaps it does occur, but people assume that the simplex algorithm is just taking too long for some other reason, and they never discover the cycling. • Researchers have developed several different approaches to ensure the finiteness of the simplex method, even if the bases can be degenerate. One such method is called the perturbation approach. The perturbation approach (in the form described here) is not practical, but it serves its purpose. It does give a way of doing simplex pivoting that is guaranteed to be finite. 15 Last Slide And that is all for our tutorial on degeneracy. We hope to see you again for our next tutorial. And I want to thank Tim, Ollie, and Nooz for sharing all of their insights on degeneracy. I also want to thank Ellen DeGeneres for making a cameo appearance. Cleaver 16