LP Special Cases

LP Special Cases

Q:What are special cases of LP?

A:They are oddities that occur in the normal operation of the algorithm. Two are opportunities and two are serious problems.

Q:Why do we need to know about them?

A:If you are using LP and one pops up, but you don’t know how to interpret it, then you have either missed an opportunity or stumbled into a serious problem and are unaware of that. Also, most algorithms have something akin to these special cases, so if you understand these, then you should be forewarned to look for and try to understand the new ones.

Q:Do we have to?

A:Yes you have to, because your sadistic professor is likely to put one or more of these special cases on your final exam.

Q:Where do we start?

A:With the following graph:

Figure 1: Degenerate Special Case Graph

Q:What do you see in Figure 1?

A:A graph of two decision variables (X and Y) and three less-than-or-equal-to constraints (numbered 1, 2, and 3). The corner points of the solution space are labeled O, A, B, and C. The graph appears to be for a maximization problem.

Q:Do you notice anything unusual about the graph?

A:At corner point B, there are three constraints intersecting at one point. Usually, a corner point has only two constraints intersecting at one point.

Q:Is this a problem?

A:No, this is one of the opportunities.

Q:Since we can’t draw a graph of most business-world problems (see, we did read the notes) how are we going to identify this opportunity?

A:You have to learn to identify it from an LP printout.

Q:Is this where we have to use all those definitions you gave us, of basic variables and slack variables, and reduced costs and all that other stuff?

A:Yes, so if you haven’t learned those definitions yet, pull out that sheet and keep it nearby.

Q:Are you going to tell us how to identify the special case from an LP printout?

A:You know it can’t be that easy. I’m going to use the opportunity to force you to understand how the LP algorithm works. In doing that, you will also learn why these special cases occur and what you can do about them.

Q:So where do we start?

A:Where the LP algorithm always starts – at the origin (maybe you didn’t read those other notes as closely as you should have).

Q:What is the list of variables for this problem?

A:You haven’t given us a formulation for the problem on the graph, so we don’t know.

Q:You should be able to get the variables from the graph, so look there and tell me, what is the list of variables for this problem?

A:X and Y.

Q:Good, and since we are starting at the origin, what are the values of X and Y?

A:They both have a value of zero.

D:Good. Let’s set up our variables in a table as we did before:

Table 1: First Solution

Q:How many basic variables do we have at this corner point?

A:Two, X and Y.

Q:Wrong. What is the definition of a basic variable?

A:A variable with a positive value.

Q:Do X and Y have positive values?

A:No, they have values of zero.

Q:So what kind of variables are they?

A:They are non-basic variables.

Q:So, how many basic variables do we have?

A:We don’t have any basic variables.

Q:Good. How many basic variables should we have (this is one of your definitions)?

A:We should have one basic variable for each constraint in the problem (excluding the non-negativity constraints) – yes, we did read the notes.

Q:Do we have a problem?

A:No, we simply have failed to list all the variables.

Q:Since we listed one variable for each axis of the graph, which variables did we miss?

A:The ones that relate to the constraints.

Q:How many constraints do we have?

A:Three.

Q:So how many (and what kind of) variables are we missing?

A:Three slack variables (you must have read those other notes).

Q:Good, and what are their values (so we can add them to our table)?

A:We don’t know.

Q:You don’t know?

A:No, because slack variables get their values from the values of the decision variables (the slack variables are dependent variables) and for that we need the constraint equations, which we don’t have.

Q:That’s true, we can’t give them specific values, but can you tell me anything about the values of the slack variables?

A:From the graph, we can tell that they all have positive values.

Q:How do you know that?

A:One of our definitions says that if a solution point is below a < - constraint line then the slack variable for that constraint has a positive value. Since the origin is below all three constraint lines, we know that all three slack variables have positive values.

Q:So what kind of variables does that make them?

A:They are basic slack variable.

Q:How many basic variables were we supposed to have?

A:Three, the same as the number of constraints.

D:What a coincidence! Let’s add them to our table:

Table 2: First Solution with All Variables

Q:What do we do next?

A:We have to figure out the reduced cost for each non-basic variable.

Q:That’s X and Y, right?

A:Right.

Q:I thought we weren’t going to calculate any more reduced costs?

A:We aren’t – I’m simply going to make them up.

D:A funny thing would happen in my lectures when I reached this point. I would do my best to get everyone’s attention, ask, “Is everyone listening to me?,” and repeat that several times – I am simply making up the reduced cost values. Inevitably, within ten minutes, someone would raise their hand to ask me where the reduced costs came from. Sometimes you just can’t win.

Q:So, what values are you going to make up?

A:The values I will make up will fit the problem as illustrated in the graph, and the relative values will be correct, as will the sign (positive or negative), but specific values are not relevant to what I am covering, so I’m not worried about that. Look at Table 3:

Table 3: First Solution - Complete

Q:Where did those reduced cost values come from (I couldn’t resist)?

A:I made them up, except, as I am sure you remember from your definitions – since you read them so carefully - the reduced cost of a basic variable (positive value) is always zero, so those were easy to make up.

Q:What does this tell us?

A:The reduced cost tells us the effect on the objective for a change in a variable’s value, so we learn that we can improve our profit (currently zero) the most by making the variable Y into a basic variable. This is illustrated in Figure 2 at the top of the next page.

Q:If we make Y a basic variable, won’t that give us four basic variables, when we are supposed to have only three (one for each constraint)?

A:Yes and no (don’t you just love answers like that?). Yes, if we gave Y some minimal value, but we will give Y as great a value as we can, so some currently basic variable

Figure 2: Y as the Entering Variable

will become non-basic. The variable that becomes basic is called the “entering” variable (it enters the collection of basic variables) and the variable that becomes non-basic is called the (are you ready for this?) “exiting” variable (it exits the collection of basic variables). Aren’t we management scientists clever at naming things?

Q:Which variable is the exiting variable?

A:As the value of Y increases, the solution point moves up the Y-axis until it hits corner point A, where it has to stop.

Q:Why do we have to stop at corner point A?

A:If we continued to move in the same direction – straight up – we would move outside the solution space, which we don’t want to do, so we stop at the first corner point we hit.

Q:How does this help us figure out which variable will be the exiting variable?

A:Let me answer that by asking:

Q:How do you determine the value of a slack variable from a graph?

A:You look at the distance from the current solution point to the constraint line.

Q:At corner point A, how far are you below constraint line #1?

A:Umm … isn’t corner point A on constraint line #1?

Q:Yes, so how far below the line are we?

A:We aren’t below it, we are on it.

Q:Right, so how far below it are we?

A:We are zero distance below the line.

Q:Exactly, and how do you tell the value of a slack variable from a graph?

A:You measure the distance the current solution point is below the constraint line.

Q:So what it the value of the slack variable for constraint line #1?

A:It must be zero.

Q:Right. Is that basic or non-basic?

A:It is non-basic, since a non-basic variable is defined as having a value of zero.

Q:So a non-basic variable (Y) became basic (entered) and the basic variable (Sl1) became non-basic (exited). Does that complete one iteration of the algorithm?

A:Yes it does. Table 4 and Figure 3 reflect the current solution.

Q:How many basic variables do we have?

A:Three, just as we should.

Table 4: Second Solution

Figure 3: Point A Solution

Q:Notice that I have put in the reduced costs for the non-basic variables at point A. Is the current solution optimal?

A:No, because the reduced costs are not all negative or zero. One of the definitions tells us that a maximization problem is optimal when the reduced costs are all negative or zero.

Q:Which variable is the new entering variable?

A:X, because it still has a positive reduced cost.

Q:What does that mean on the graph?

A:We will move along constraint line 1 to corner point B. Variable X will increase in value and variable Y will decrease in value a little. We know this trade-off is worthwhile because the reduced cost is positive.

Q:How will we identify the exiting variable?

A:Look at corner point B and see which constraint lines we are one at that point

Q:So, which constraint lines are we on at corner point B?

A:We are obviously still on constraint line #1, but we are also on constraint lines #2 and #3, since all three intersect at that one corner point.

Q:What does that tell you about the values of the slack variables?

A:All three slack variables (Sl1, Sl2, and SL3) will have a value of zero. This is shown in Table 5:

Table 5: Optimal Solution

Q:How many basic variables do you have?

A:Only two.

D:That is what makes this a “degenerate” solution. In this setting degenerate means simply that an algorithm breaks down (it does not mean the same thing as when you parents use that word to refer to you). Expecting three basic variables, because there are three constraints, and finding only two, the algorithm would simply stop at this point, unless it had a trick for getting around this problem. The trick is simply to treat one of the non-basic variables as if it were basic. This creates the problem that a variable labeled as basic actually has a value of zero, but the computer can live with that.

Q:What caused this to happen?

A:Constraint line #3 is redundant.

Q:What does that mean?

A:It means that if constraint line #3 were removed form the graph, the shape of the solution space would be unchanged. A redundant constraint line is usually far removed from the solution space, not touching it at all. In this case, it was tangent to the solution space, which caused all the trouble.

Q:Could we get rid of this problem simply by removing the constraint?

A:You could, but only because we have a graph to look at. Without a graph, it is very difficult to identify a redundant constraint, so we mostly don’t bother to try.

Q:So how do we identify this special case from an LP printout?

A:Look for a variable that is labeled as “basic” (most printouts do this), but has a value of zero (contrary to the definition, which is that basic variables have positive values).

Q:You called this an opportunity. Why?

A:Opportunity might be too strong a word, but it certainly is nothing to worry about. Think about the normal result for a problem like this. If only two (out of three) constraints intersected at each corner point, then any solution would have one of the three constraints with leftover units. With a degenerate solution, the third constraint is also fully used, which from a business point-of-view would have to be considered a good thing, and thus an opportunity. Don’t brag to your boss about it, though. Unless your company operates on a just-in-time basis, this was simply luck, and you may not be able to make it happen again.

Q:Does that finish the first special case?

A:Yes it does. The next one is even more of an opportunity, if you have the wit to take advantage of it. Also, the next presentation will go faster, because I am going to assume that you have grasped the definitions that I drew out so laboriously in the first presentation. I will only go into detail for any newly defined terms.

Q:So what does the graph look like for the next special case?

A:It looks like this:

Figure 4: Alternate Special Case

Q:What do you see in the graph in Figure 4?

A:Again, a maximization problem with two decision variables (X and Y) and three < constraints. The constraints are numbered, the corner points of the solution space are labeled A through D, and the objective function is indicated as a dotted line. The initial solution is indicated as the origin.

Q:Good. Do you see anything unusual about this graph?

A:Not really, no.

Q:How do we get started, then, working through the algorithm?

A:You show the solution at the origin, as in Table 6:

Table 6: First Solution - Complete

Q:Is the current solution optimal?

A:No, because the decision variables both have a positive reduced cost, which tells us the total profit would increase if gave one or both of these non-basic variables a positive value.

Q:What happens next in the algorithm?

A:Well, we have evaluated the search directions (calculated the reduced costs), so we pick the search direction (non-basic variable) with the best reduced cost, which would be X, and create a new solution where X has the highest value it can get.

Q:What would that mean on the graph?

A:We move to the right on the X-axis until we reach corner point D, as shown in the following table and graph:

Table 7: Second Solution

Figure 5: Second Solution

Q:Is the solution at corner point D optimal?

A:No, because there is still a positive reduced cost (effect on the objective) for one of the non-basic variables (Y).

Q:What comes next?

A:We increase the value of Y, and according to the graph, decrease – slightly – the value of X (which is a worthwhile tradeoff because the reduced cost is positive), until we arrive at corner point C, as shown in the table and graph at the top of the next page.

Q:Is the solution at corner point C optimal?

A:Yes, because all the reduced costs are negative or zero, so there are no further improvements in the objective function to be found.

Q:So where is the special case?

Table 8: Optimal Solution

Figure 6: Optimal Sol’n

A:Look carefully at the reduced cost values for each variable and look for anything unusual.

Q:Is it unusual for a non-basic variable to have a reduced cost of zero?

A:Yes, it is.

D:A basic variable has a reduced cost of zero because it can have no further effect on the objective (it is already at its maximum value). A non-basic variable, if it were to become basic, would be expected to have SOME effect on the objective, either an improvement (meaning you have to do another iteration of the algorithm) shown by a positive value, or a negative value showing the objective would get worse (meaning you are finished).

Q:What does a reduced cost value of zero for a non-basic variable tell us?

A:It tells us that we could make the non-basic variable into a basic variable and there would be no change at all in the objective function value.

Q:Wouldn’t making a non-basic variable into a basic variable move us to another corner point, meaning we have a different solution?

A:Yes, and that is what makes this a special case. Normally, LP gives a single solution (corner point) that is THE optimal solution. If you change the solution at all, then you give up some profit (or increase cost). In the alternate special case, though, there is more than one corner point with the exact same total profit (or cost), so you get to choose.

Q:How can two corner points have the same total profit?

A:Look at the graph. Notice the objective function (the dotted line) is parallel to the second constraint line. That means every point on constraint line #2 will have the exact same total profit. Since corner points B and C lie on constraint line #2, they both have the same total profit. We happened to find corner point C first, and since no further improvements were possible, the algorithm stopped. If, however, we forced the algorithm to move on to corner point B, we would move from being on constraint line #3 (Sl3 is used up, non-basic) to being on constraint line #1 (Sl1 is used up, non-basic). Thus Sl3 enters the basis while Sl1 exits, a normal iteration except that the objective function doesn’t change.