Thursday, April 19, 2012

Model is infeasible or unbounded

My favorite return code from an LP/MIP solver is:

MIP status(4): Model was proven to be either infeasible or unbounded.

Come on guys, you really can do better than this! OK, what to do as a user? My simplest suggestion – using GAMS – is to add a bound on the objective variable and solve again:

z.lo=−1e10;
solve m minimizing z using mip;

Now at least we see:

MIP status(3): Model was proven to be infeasible.

If the model was actually unbounded you would have seen large numbers in the solution, making it easy to find out what was wrong.

Note: Please don’t tell me “dual infeasible” is a good return code. That is just another name for the same thing, and just as useless for a modeler. If you are working on a model you really want to know if the model is infeasible or unbounded. I understand it is an easy way out for the algorithm-developer to return something like “dual infeasible” (I have heard some users saying that is just laziness, and I understand that sentiment). The return code should really relate to the model and not what is the easiest for the algorithm-developer to implement.

Not everyone agrees with these opinions (see the comments).

The model was fairly small. If we compare the time both the user needed to email me the question and the model, for me to look at it and respond (say in total half an hour) and the time the solver would need to spend to get a better diagnostic (let’s say 0.1 seconds) then we can say a huge efficiency gain is possible here.

9 comments:

  1. In my opinion it's because the optimizer should not return "Unbounded". There should only be primal or dual infeasible return status, which is what we use in our software. The problem arise in situations where you don't know if the primal or dual feasible region is empty or not. For instance in presolve you can prove there exists no dual feasible solution, but to say it's unbounded you will need to make sure the primal feasible region is not empty.

    ReplyDelete
  2. One of the reasons to not using a dual infeasible status is of course legacy, but also that many users don't know about duality and the farkas ray theory it leads to. Just like users want the SOLUTION and not the primal solution :-)

    ReplyDelete
  3. "Please don’t tell me “dual infeasible” is a good return code."

    I did not say it was good, but I definitely think it's better. And it's not because developers want the easiest way out.

    "If you are working on a model you really want to know if the model is infeasible or unbounded"

    I agree, but in many situations there is no way around rerunning a modified version of the model to be sure. If you did that by default it would be time consuming for users not wanting this feature.

    ReplyDelete
    Replies
    1. @Bo: Well said. Then again, one could make rerunning the modified version the 'standard behavior' and give power users the option to turn it off. Not sure which is better...still thinking which I like better for the Optimization.Framework.

      Delete
  4. I've thumped the following drum before, but what the heck, I'll do it again: all variables in all practical models should have finite bounds (and by "finite" I mean less than whatever huge value your solver equates with infinity). That way, the primal problem is never unbounded, so "infeasible or unbounded" will translate to "infeasible". If any primal variable hits an arbitrarily created bound, the modeler should look at whether the bound was chosen too tight or whether the model is trying to be unbounded (implying, to me, a defective formulation).

    Bo raises good points about what happens in presolve (as opposed to when you are staring at the equivalent of a terminal simplex tableau). To narrow down the result, you have to spend additional computational time, and it's not clear the user wants to spend that time. Personally, I would; but someone else might assume "infeasible or unbounded" means an error coding the model, and would be happy to stop there and start proof-reading the code.

    ReplyDelete
  5. I probably should add that, my previous comment notwithstanding, I do find the "infeasible or unbounded" message a PITA when helping other people with their models, since I typically have no intuition whether someone else's model is infeasible versus unbounded.

    ReplyDelete
  6. Assume you solving a MIP (the case of Erwin). Now assume that the initial relaxation is unbounded. What can you concluded then? All you can conclude is that the problem is unbounded or infeasible. You would have to do a phase 1 problem to make a different conclusion. Most users would not like that I think.

    So in my opinion there is a good reason why MIP codes report as they do.

    Talking about dual infeasibility only make sense in the continuous case. Please note that dual simplex usually would say dual infeasible and not unbounded because it does know whether the problem feasible or not.

    ReplyDelete
  7. Sure, dual infeasiblity only makes sense for the continuous case, I was talking about LP.

    ReplyDelete
  8. Quick question:
    "all variables in all practical models should have finite bounds"

    Wouldn't this also compromise performance in some way (even if slightly)?

    I am 100% behind Erwin on this one, a better analysis is valid.

    ReplyDelete