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.

Bin Packing Made Easier?

I have always found the following example interesting. I remember that it was Peter Ross who first showed me this during a presentation at a conferenec we were both attending.

The example demonstrates that an algorithm can act in an unexpected way when you make a very small change to the input data.

The example is drawn from bin packing. In this problem, you are given a number of items, all of which have a weight. Let's assume that we have the following 33 items.

442, 252, 127, 106, 37, 10, 10, 252, 252, 127, 106, 37, 10, 9, 252, 252, 127, 85, 12, 10, 9, 252, 127, 106, 84, 12, 10, 252, 127, 106, 46, 12, 10

We are also given an infinite number of bins, each one having a certain capacity. Let's assume that the capacity of our bins is 524.

The aim is to pack all 33 items into as few bins as possible.

How would you do it? What algorithm would you use?

One possible algorithm is as follows:

1) Sort the items into descending order of size, thus:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9


2) Take each item in turn and place it into the first bin that will accommodate it. The bins are also considered in the order they were first used.
So, to start we have no bins available, so we open one. We take the first item (442) and place it in that bin. Now we take the next item (252). We cannot fit this into the bin we have just opened (as 442+252 > 524) so we open another bin.
The next item (252) will be placed in the second bin. The next item (252) will have to open a third bin.

... and so on.

If you apply this algorithm, you will get this solution

Bin 1: 442, 46, 12, 12, 12 = 524
Bin 2: 252, 252, 10, 10 = 524
Bin 3: 252, 252, 10, 10 = 524
Bin 4: 252, 252, 10, 10 = 524
Bin 5: 252, 127, 127, 9, 9 = 524
Bin 6: 127, 127, 127, 106, 37 = 524
Bin 7: 106, 106, 106, 85, 84, 37 = 524

You'll notice that we have a solution that requires 7 bins and, moreoever, each bin is completely full. Therefore, we know we have found an optimal solution.

As an aside, what we have just done is used a heuristic (a rule of thumb). This one is known as Largest Fit, First Fit. We could come up with many more. For example, we could sort the pieces in different ways, we could consider all the open bins before deciding which one to use etc.

The question now arises, is the largest fit, first fit heuristic always the best heuristic to use for the bin packing problem?

Let's see.

Take our list of sorted items again. That is:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

But this time remove an item (say 46 - which has been removed from the list above).
We know that we can use seven bins to pack these items, and have 46 units left over.

So, let's apply the largest fit, first fit heuristic and see what happens.

This is the result.

Bin 1: 442, 37, 37 = 516
Bin 2: 252, 252, 12 = 516
Bin 3: 252, 252, 12 = 516
Bin 4: 252, 252, 12 = 516
Bin 5: 252, 127, 127, 10 = 516
Bin 6: 127, 127, 127, 106, 10, 10, 10 = 517
Bin 7: 106, 106, 106, 85, 84, 10, 10, 9 = 516
Bin 8: 9 = 9

This is quite surprising (well, it is to me). We have removed an item, but had to use an extra bin.

Of course, we could develop another heuristic that only used 7 bins, but would that heuristic work well on other problem instances? Or, to put it another way, if you were presented with an instance of a problem you had not seen which heuristic would you use?

There is some work being done in an area termed hyper-heuristics (which I'll blog more about in the future) which is trying to address problems such as those described above.

If you are interested in reading more about hyper-heuristics, you might like to visit my publications page (http://www.cs.nott.ac.uk/~gxk/gxk1/publications.html).

Good introductory articles are:

1. Cowling P., Kendall G., Soubeiga E.A Hyperheuristic Approach to Scheduling a Sales Summit. In LNCS 2079, Practice and Theory of Automated Timetabling III : Third International Conference, PATAT 2000, Konstanz, Germany, August 2000, selected papers (eds Burke E.K. and Erben W), Springer-Verlag, pp 176-190, ISBN : 3-540-42421-0
2. Burke E.K., Kendall G. and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics , 9(6), 451-470, 2003
3. Burke E., Hart E., Kendall G., Newall J., Ross P. and Schulenburg S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Handbook of Meta-Heuristics (Glover F., ed), pp 457 – 474, Kluwer