Let's Talk About Infeasibility, Shall We?

I Think Many of You Are Dealing with It Improperly

In my work as a consultant, I'm often presented with models that aren't working as the client intended. That means I get to see how the model has been formulated and how the analysis has been done. And frankly, its a bit shocking sometimes what passes for a preferred alternative among a bunch of scenarios. Clearly, some of you don't really understand infeasibility and the proper way to deal with it.

What Do Feasibility and Infeasibility Mean?

In every constrained linear optimization model (i.e., LP, MIP), there must be a set of constraints in place that define a convex feasible region. Convexity just implies that there is a smooth gradient such that there are no local optima present. In the following example, the blue lines represent a convex feasible region for a minimization problem because there is only one minimum point (global optimum). The orange region is not convex because there are two local optima visible:

Feasible Regions for 2 Minimization Problems

If we have a convex set of constraints (red lines and direction of inequality) and an objective function (dashed line), we can search the corner points of the feasible region (pale green) and locate the minimum corner point, which is the global optimum. We have a feasible and optimal solution.

Locating the optimal solution

Suppose we add another constraint. Now, there is no feasible region because there is no overlapping area where the constraints can be met simultaneously. The example is patently infeasible:

Patently Infeasible Problem

If you look at the graphic, you might be wondering why someone would propose a constraint that so obviously cannot be met. Good question. However, some of you are doing this all the time. Years ago, I worked on a project for the US Forest Service. They had 9 structural stage conditions that they wanted constrained to be in fixed proportions of the forest. Think about that - how do you maintain a static structure in a dynamic forest? The youngest stands grow out of earlier structural stages into later ones. The only way to replace them is through harvesting. Alas, the earliest structural stage lasts 20 years, but it takes more than 120 years to reach the latest structural stage. You don't need an LP to determine that the desired outcome is patently infeasible.

Ah, But What About Goals?

Yes, goal formulations are very useful when trying to mitigate infeasibility, but you have to use them correctly. Many of you are not.

How Do Goals Work?

Let's say you have a constraint requiring 5000 acres of some type of habitat:

oaCaribou >= 5000 1.._LENGTH

If you know the characteristics of the habitat, you should be able to determine if at least 5000 acres currently exists in the forest. If it doesn't, your constraint is patently infeasible. The more interesting question is, can we improve the situation over time? If so, we need to know by how much and how long will it take? Finally, once we achieve the desired acreage, can we sustain it? 

From the models I have reviewed over the years, I know at least some of you are addressing this problem by applying goals. A goal applied to a constraint simply introduces slack and/or surplus variables to eliminate the infeasibility. For our example, the habitat constraint becomes this:

oaCaribou + Slack = 5000 1.._LENGTH

If oaCaribou is less than 5000 in any period, the variable Slack takes on the value of the shortfall. But since Slack is a free variable (not tied to land or activities), it could take on any value greater than zero and less than or equal to 5000. In other words, the model could harvest qualifying habitat and simply make Slack larger. To avoid this outcome, we need to penalize the use of Slack so that it only is used when there is no alternative. Said another way, we want the solver to enforce the constraint unless it is impossible, and then only to the degree required. If you think about it, this is a minimization problem. The correct way to deal with the goal is to minimize Slack, subject to the constraint.

*OBJECTIVE

_MIN Slack 1.._LENGTH

*CONSTRAINTS

oaCaribou + Slack = 5000 1.._LENGTH

If we solve this LP, we will know the total acres of shortfall across the entire planning horizon (objective function), as well as the shortfalls in each planning period (Slack). Now that you know where the shortfalls are, you can adjust the RHS values for each period down to where the constraint is just feasible. You know you can't improve the objective function which means the sum of the shortfalls cannot be improved. How do we know this? If there were a way to reduce the sum of shortfalls, then the solver would have found it. Now, there may well be alternative optimal solutions where the shortfalls are different in different planning periods, but the sum across all periods will never be less. We will return to this idea in a future blog post.

So Why Do So Many of You Leave Goals in Place?

I've reviewed models that are supposed to be preferred alternatives from a bunch of scenarios that were run, and they look like this:

*OBJECTIVE

_MAX oqTotal - _PENALTY(_ALL) 1.._LENGTH

*CONSTRAINTS

oaPL_OG - 0.045 * oaPL >= 0 1.._LENGTH _GOAL(G1,9999)

oaSB_OG - 0.045 * oaSB >= 0 1.._LENGTH _GOAL(G2,9999)

oaSW_OG - 0.045 * oaSW >= 0 1.._LENGTH _GOAL(G3,9999)

oaMX_OG - 0.045 * oaMX >= 0 1.._LENGTH _GOAL(G4,9999)

oaOC_OG - 0.045 * oaOC >= 0 1.._LENGTH _GOAL(G5,9999)

oaHW_OG - 0.045 * oaHW >= 0 1.._LENGTH _GOAL(G6,9999)

First off, there's our shining example of a patently infeasible problem, made that much worse by embedding the penalty function for the goals in the objective function, and by using arbitrary large goal weights. The use of goals implies that missing the target is generally achievable, but sometimes you miss. How is that working out? Let's look at the goal summary that Woodstock produces as part of the SCHEDULE section:

; Constraint: oaMX_OG - 0.045 * oaMX >= 0 1.._LENGTH

; Period    Period    Above    Below    

     5         5               1687.7        ; C1R11

     6         6               1687.7        ; C1R12

     7         7               1687.7        ; C1R13

     8         8               1684.3        ; C1R14

     9         9               1463.2        ; C1R15

    10        10                501.6        ; C1R16

    11        11                463.8        ; C1R17

    12        12               1687.7        ; C1R18

    13        13               1687.7        ; C1R19

    14        14               1687.7        ; C1R20

; Constraint: oaSW_OG - 0.045 * oaSW >= 0 1.._LENGTH

; Period    Period    Above    Below    

     6         6               8412.8        ; C9R6

     .         .                   .         .   .

     .         .                   .         .   .

     .         .                   .         .   .

    20        20               8412.8        ; C9R20   

Clearly, the constraints are only working for the first few periods before shortfalls appear. In the case of oaPL_OG, you are always 8412.8 ha short after period 5. So why not adjust the RHS values and accept that your policy objective is set too high?

And what about the objective function value, that is supposed to maximize total harvested volume? Well, that works out to be -3.38583928E11, or negative 338.5 billion. Is that in cubic meters? No, because it includes the sum of penalties across all the constraints, some of which is measured in hectares scaled by an arbitrary value of 9999. The objective function is meaningless other than to show that the sum of penalties completely swamps any actual harvest volume.

Please Stop Abusing _GOAL

If you work for a public lands agency and your policy directives are never achievable, why is your agency keeping them in place? Did you not do any analysis ahead of time to determine if such policies were feasible? If you are approving management plans based on model solutions that still incorporate goals, why are you doing that? If you work for a consultant or timber investment management organization, you probably have fewer policy directives to consider. Still, you need to be honest about your assumptions. If you apply goals to constraints on minimum product harvest volumes or cash-flow positivity constraints, you're simply masking the fact that you're violating these constraints. And if every constraint in the model has goals applied to them, do you really know if any of them would be feasible absent the goals?  If you're answering "I don't know" or simply "no" to any of these questions, I'd suggest you're not doing your job as well as you should. If constraints truly are infeasible, you should be honest about it and your model should reflect the true state of things. Otherwise, someone like me will call BS and do "the emperor has no clothes" thing. We will continue this discussion about constraints and infeasibility next time.

Contact Me! 

If you would be interested in a training session on how to properly do harvest scheduling analysis using goals and other techniques, let me know. And if you have any comments about this blog post, or ideas about future blog posts, add them to the comments section.