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!