Clearly, if you can model a problem as an ILP and solve to optimality, then you can do no better. By contrast, heuristic solutions typically call short of the optimal. My experience is that some researchers tend to assume that ILP (or equivalent techniques with optimality guarantees) will therefore lead us to actual optimality in practice, and are the first thing to try, and will do better than anything else, etc i.e. ILP is "the bees knees". Heuristic solutions, on the other hand, are perceived as "risky" - we don't know for sure how good they are, maybe they behave unexpected in uncharted scenarios, and so on - we have entered the world of the Dark Arts. Giving up on optimal solutions in favour of heuristic solutions is done begrudgingly and seen as a sort of failure, to the point where "heuristic" is a dirty word. In practice however, grappling with complicated, large problems, it seems to me that the downsizes of using ILP are rarely acknowledged or even recognised: 1) To model a problem as an ILP it is often necessary to simplify it considerably - eg. remove details, remove stochasticity, introduce rounding assumptions and so on. The optimality attained only applies to the simplified problem, not the original problem, so the solution is only as good as your set of simplifications! 2) For large problems, it seems fairly standard to allow an optimality gap of 1%-5%, weakening the optimality claim (by a bounded amount). 3) For large problems, ILPs can be excruciatingly slow. In any real world practical setting, a computational time limit is essential so a business isn't waiting, say, 48 hours to get this morning's scheduling plan. We can empirically estimate the typical optimality gap for a given time limit but there are no guarantees around this. So in practice, apart from the (rare?) case where your ILP model a) genuinely represents the full problem; and b) consistently solves to optimality in an acceptable amount of time, it seems to me that ILP - in practice - is vulnerable to the same criticisms of heuristic solutions. In general we do not attain optimality for the full problem and the actual gap in practice may be unknown(/able) and variable. Furthermore, my experience in the commercial world is that companies want improvement, rather than global optimality. Most business owners would say it is better to save $1M with a heuristic solution than spend 6 months chasing after globally optimality, which may not deliver a practical implementation in the end. I am relatively new to OR and my opinions are certainly biased around the projects and teams I happen to have worked with so far. Can you share more about your experiences working on real world problems, delivering practical and scalable solutions, and the attitudes around heuristic vs. ILP(/other optimal) approaches?
asked
brendanhill |

As an academic, I have limited experience working on real-world problems (and even less on having my solutions implemented), so take this for what it's worth. I generally agree with what you said, with one qualification. If you solve an ILP with a suitable time limit ("suitable" meaning "get an answer in time to be useful") and a reasonable gap limit, ILP in effect becomes a heuristic with a bound on suboptimality (and a shot at provable optimality, subject to your valid point that the model is not a perfect representation of reality). The gap bound is the one thing a plain old heuristic won't typically provide, and it may be useful to management. I think you're right that management often just wants improvement, but even then a gap estimate can be helpful in deciding whether to run with the current solution or sit back and let the computer grind some more. Also, the two are not mutually exclusive. You can run a heuristic or metaheuristic to get a "good" solution, then use that as the starting point for an ILP solver. With a lot of heuristics, improvement slows down as the solution quality improves (meaning after you've plucked the low hanging fruit). It might be that the ILP solver can squeeze out a few more improvements faster than continued use of the heuristic can. I tend to believe that running an ILP solver to optimality (zero or near zero gap) on "practical" problems is not often very useful, other than in cases where you get there quickly. Much of the tail of a long run is often spent proving the optimality of a solution you had hours ago.
answered
Paul Rubin ♦♦ |