Monday, October 3, 2011

MIP caveats

In a number of caveats when doing MIP modeling are listed:

  1. All 0 objective: although it should be easier to find any solution than one specific, in certain situations it might pay off to add a fake objective function to guide the search. Anything reasonably stable should work and preferable all variables would have different objective coefficients. This sometimes works, sometimes not. I guess it also has to do with the fact that solvers usually detect this and do something about it.
  2. Unstable objective: Very big and very small coefficients in the objective function, especially values below the dual tolerance, can cause issues with dual feasibility and very unexpected results.
  3. One or few objective coeffcients: One can observe that MIP solvers have trouble solving instances with only one (or a few) non-zeros in the objective function. At least part of the problems with these models is dual degeneracy.

Point 1: I am not sure about this one. With Obj=0 we really want to stop as soon as a feasible integer solution is found. With an obj<>0 this is no longer the case (or am I misreading this; may be additionally the stopping criterion “stop after first feasible solution” is implied). I don’t have many MIPs without an objective (and first integer solution found is not always very good), so my experience is limited. Somehow I feel this would need more empirical evidence.

Point 2: agreed. E.g. with long planning horizons (like in forestry models) some of the reduced cost can become very small. Playing with LP optimality tolerances can help in such cases (I usually don’t want to touch those, but this is an exception).

Point 3: I don’t understand that completely. I have many MIPs with very few cost coefficients (often just one: e.g. max profit). I have seen cases where small “random” obj coefficients can help to break symmetry and force solutions to be different. But that is different than is described here.

I.e. in general these are not the problem areas I would quickly consider if I have a difficult MIP. Either this user has access to different solvers than I do or he is solving different types of models. Or both.

Anyway, it is interesting to see I have such a different experience about problem areas in MIP modeling. I also think that many “older” tricks (such as I mentioned under point 3, another one is using priorities) are more and more becoming obsolete due to smarter and more sophisticated MIP solvers. I have a few “old” models with some tuning tricks, that really nowadays solve faster without all the tricks.