Can we call a heuristic (especially a meta-heuristic) a solver? I am not so sure.
Warning: this is somewhat of an opinionated rant. Many of you may not agree.
The name "solver" seems to imply that the underlying algorithm knows when an optimization problem is solved. By that I mean: it can stop at some stage and report "solved". Meta-heuristics typically don't have a clue about optimality, and just keep on churning until hitting some form of time or iteration limit. (One could devise some stopping criteria basic on stochastic reasoning, but that is not often used in meta-heuristics).
So my proposal is:
Heuristics (including meta-heuristics) should not be called solvers. They don't know when a problem is solved.
Recognizing a problem is actually solved can take different forms. E.g.
- A local NLP solver will stop when a solution is a local optimum.
- A MIP solver can stop when the solution is not more than x% from the optimal solution. (Stop on gap).
- Solvers may be able to report proven global optimality.
- Maybe a local search algorithm can be called a solver: like a local NLP solver, it may be able to deliver solutions that have no better solution (proven) in a given neighborhood.
Meta-heuristics don't know anything about optimality, so they really cannot stop with the message "solved". Of course, we can redefine the problem as: give me a good solution. Heuristics do not know about what good is either. So we have to relax this further to "not too bad" in the sense that it made some improvements, so it at least skipped some really bad solutions. That is about the only (deterministic) thing a heuristic can say.
Looking at the discussion in [1], I am in the minority on this. Solvers may be just algorithms that deliver "solutions" (where solutions mean points). Would that mean that a random number generator is a solver? So maybe a solver is an algorithm that provides "useful solutions". That is a bit vague.
I think that we may be overpromising on the capabilities of heuristics by calling them "solvers". Solvers should at least be able to return "problem solved". Of course, for large problems, a MIP solver may not be able to find proven optimal solutions. In [1] someone argued: so then a MIP solver is no solver. I find that a silly argument: a MIP solver degrades gracefully in capabilities for large problems. For small problems, it can provide proven optimal solutions. For larger problems, it can stop on a gap, or when stopped early, provide bounds. What else do you want from a solver?
Optimality is more difficult than feasibility. Many models solved with meta-heuristics handle constraints by putting them in the objective with a (fixed) penalty. The algorithm itself does not know about constraints or about feasibility. (I have seen a supplier of a meta-heuristic call his system a "constraint solver"; that is a bit optimistic if your algorithm does not know a thing about constraints). Of course, as a user, we can evaluate whether the solution returned was feasible by checking all constraints. That, in general, is not possible w.r.t. optimality (for some classes of models we can check optimality conditions).
Finally, I want to add that heuristics are not the same as approximation algorithms. Approximation algorithms give some sense of closeness to the optimal solution. In that sense, a MIP solver with a gap is an approximation algorithm. A heuristic does not give any bound (apart from using a statistical argument).
Of course, all of this does not say that heuristics are not immensely useful. They are. But we should not attribute properties to them that they can not fulfill. Of course, we see this also in other areas. The term AI is used for many standard optimization models and algorithms such as neural networks, giving them magical capabilities, opposed to saying "we find a local optimum for a well-defined mathematical model".
Maybe "solver", just like AI, is just a marketing term. I think, however, that it would be better that a solver can actually solve a stated problem.
No comments:
Post a Comment