Monday, April 5, 2021

This is really a modeling issue

 In [1], the following scenario is described:

  1. A MIP model is solved, delivering a feasible solution.
  2. All integer variables are fixed to their levels.
  3. The resulting LP model is solved in order to produce duals. This model turns out to be infeasible.

I have seen this behavior on multiple occasions. The cause is not easily described: it has to do with slightly different numerics between the original MIP model and the fixed LP. The problem is borderline infeasible. This means it is somewhat random whether a solver will declare it feasible or infeasible. Which in turn explains why in one case it is infeasible and the other it is feasible. There is no good "technical" fix. We can relax the feasibility tolerances in the second LP, but that is haphazard. By how much? How much will this change our duals?

A better strategy is to prevent this situation from happening in the first place. In my opinion, it is much better if production models never are infeasible. Infeasible models often don't produce a solution at all, so we cannot look at things. Mechanical tools like IIS (finding small subsets of equations that make the model infeasible) are overrated in explaining infeasibilities: these subsets are often just not the real explanation and are not intuitive for an end-user. We can achieve better behavior by making the model elastic.

In an elastic model, we replace some of the hard constraints with soft constraints. This often makes economic sense: throwing money at a problem can almost always make it go away. Here are some examples:
  • If running out of storage capacity, rent expensive extra capacity.
  • If we cannot deliver orders on time, allow being late at a cost.
  • If we have a capacity shortage in production capacity or personnel, allow expensive outsourcing or hiring of temps or pay for overtime.
Typically we keep the "physical" constraints as hard constraints. This includes constraints that describe a proper schedule (e.g.: we can only run one job on a machine at a time).

With such an elastic formulation we achieve that the solver will never say "infeasible, no solution". Or my favorite message: "Infeasible or unbounded." (Solvers do not always minimize the time the user has to spend on deciphering error messages). It always produces a solution that can be inspected. This solution may show the use of expensive extra resources. This emergency usage is minimized by the solver (so it makes sense). An end-user can see that we exhausted our normal resources and had to use these emergency resources to make a schedule or plan.

Back to our original problem. We can after the first MIP solve inspect the solution. If all expensive, emergency resources are not used we are happy and can form the LP. This will always be feasible (if needed it will use a tiny little bit of emergency resources to make things work: that can be ignored in practical cases). If the first model is "infeasible" (i.e. we use emergency resources) we can choose not to solve the second LP, or we just can solve the LP anyway. The meaning of the duals is slightly different in this case: it will refer to an objective with the expensive emergency resources in use. But knowing that this objective is used: these duals are correct!

Conclusion: there are really good reasons to form elastic models. They can help us in building robust optimization applications that are not as sensitive to oversubscribed situations and always yield solutions that can be interpreted. And some advice: drop the urgency to tinker with tolerances. These problems are much better attacked at the modeling level.




  1. My colleague Ed Klotz has a nice rule of thumb of cases like this: the lowest significant digit in your coefficients should be a factor of 10 larger than the feasibility tolerance of the solver. The case you are describing sounds a lot like a case where this rule was not respected, and then, as you rightfully point out, all "hell" can break loose.

    1. I think I have seen this behavior also for some models with more "normal" data. Of course, after scaling/presolving I don't really know anymore how the input data looks like.