Constraints and Feasibility

All Constraints Are Equal...
       But Some Are More Equal Than Others

Apologies to George Orwell, but the way some people view constraints puzzles me. To an LP solver, all constraints are equally important in that a feasible solution must respect all of them simultaneously. However, as modelers we must recognize that in terms of real-world significance, all constraints are NOT equally important. 

Woodstock Constraints Are More Complicated Than Meets the Eye

Consider a simple Woodstock constraint with a 50-period planning horizon:

oaHABITAT >= 5000 1.._LENGTH

This statement represents not a single constraint but 50 of them with 50 accounting variables:

oaHABITAT[1] > = 5000

oaHABITAT[2] > = 5000

oaHABITAT[3] > = 5000

         ...

oaHABITAT[48] > = 5000

oaHABITAT[49] > = 5000

oaHABITAT[50] > = 5000

What we see as oaHABITAT in Woodstock is really an array of accounting variables, indexed by planning period. For each accounting variable, there is a target value to achieve and a planning period in which to do it. Two questions come to mind for just this single output: how important the target value is and are later planning periods as important as earlier planning periods? You should also be considering the other constraints in your model in the same fashion. 

How To Determine Relative Importance

Relative importance should be fairly easy to discern:

1. Legal requirements
2. Contractual requirements
3. Policy requirements
4. Financial requirements
5. Desirable outcomes

If you are required by law to maintain some condition and you can reasonably model it, these are the constraints that you should verify first. Next, you may have some contractual requirements (say, a volume of wood products) that necessarily must be met. Organizational policy requirements should come next, followed by any financial obligations your organization may have. Finally, constraints that represent desirable rather than necessary outcomes should come last. If you formulate a model with all the constraints in place and it solves, great! But if it doesn't solve, then you need to determine where the problem is, by going back to your hierarchy and running scenarios! Don't just slap goals on everything and call it good!

Mitigating Infeasibility

Last time, I suggested that a goal formulation could be used to determine the minimum shortfalls in potential habitat. For example, in this case we could use:

*OBJECTIVE

_MIN _PENALTY(_ALL) 1.._LENGTH

*CONSTRAINTS

oaHABITAT >= 5000 1.._LENGTH _GOAL(G1,1)

If the solution meets or exceeds 5000, the goal penalty is zero, otherwise the penalty is 1 per hectare of shortfall. If we graph oaHABITAT over the planning horizon, we see this outcome:

Significant Shortfalls in Early Periods with Reversal

We know there is no solution where we can reduce the total shortfall area across the planning horizon. However, this is a situation the timing of the shortfall matters as much as the amount. By Period 10, the shortfall is gone but it returns in Period 16 for four periods. Perhaps, it would be better to have more shortfall early on and then no shortfalls at all. How could we effect that outcome?

We use discounting in financial models to reflect the time value of money: revenues in the future are worth less to us now than current revenues. If we turn that logic on its head, we could use lower penalties early on and higher penalties later to show that shortfalls in the future are more problematic. Unfortunately, Woodstock doesn't offer an easy way to automatically increase goal weights, but we can write constraints directly using a FOREACH loop:

FOREACH xx in (1..50)

oaHABITAT >= 5000 xx _GOAL(Gxx,xx)

ENDFOR

We have to write explicit planning periods, goal_IDs and weights, but luckily, we can just use an increasing series of numbers from 1 to 50. Now, every subsequent period increases the penalty on shortfalls. While the total amount of shortfall may increase, the period of shortfall should be as short as possible:

Higher Shortfalls Early, No Reversals

The second scenario (Series 2) increases the total shortfall over the planning horizon from 12,845 to 12,857, but it does so without reversals:

A Tradeoff Between Total Shortfalls and Reversals

Supposing that habitat is a legal requirement, and we know of a strategy to eliminate shortfalls within 10 planning periods, we should adjust the constraints to reflect these achievable habitat values and remove the goal formulation. Any additional constraints will have to maintain these habitat levels.

Summary

In this post we considered the relative importance of different kinds of constraints as well as the importance of timing of outcomes. Rather than relying on blanket goal formulations and default weights, we applied some logic to the situation to devise an improved solution. Unfortunately, not every situation will work to your favor. It may turn out that increasing weights over time has no effect on shortfalls, but at least by trying you know this to be true.

Contact Me!

If you'd like some help with a tricky formulation, or you'd like to engage in a custom training for your team to improve their analytical skills, give me a shout. And again, if there's something you'd like me to cover in a future blog post, let me know!

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.