How General is Your Algorithm?

One of the research issues that has been tackled for at least 50 years is attempting to develop algorithms that are better than other algorithms on a certain type of problem (for example, vehicle routing, traveling salesman problem etc.). And it is easy to judge if you have a better algorithm. You run it on a benchmark problem from the literature and if yours is better you write a paper claiming as much. Of course, you should also show statistical significance, robustness of your approach, provide some discussion etc.

There has been some recent work where the goal is to develop an algorithm that works well on many different problem domains. This is a challenging objective as even small changes to a problem instance can make an algorithm that used to perform well, now perform poorly. See a previous blog where I gave a simple example.

So, if we have an algorithm that works well on a particular problem instance, but a small change to the problem renders it useless (or at least worse than it was) then imagine the challenge in trying to get an algorithm to work on a totally different domain without any changes being made to the algorithm. To make it clearer what we are trying to achieve, let’s say you have an algorithm that works well on a Vehicle Routing Problem. Is it possible, without any changes to that algorithm, to get it to work well on a (say) a staff rostering problem?

This is one (if not THE) goal of hyper-heuristics. In a future blog, I’ll give some more concrete examples, but the challenge of developing more general search algorithms is an area that is attracting quite a lot of interest at the moment.