The curse of the benchmark instances

Question

Many problem areas (like vehicle routing, hub location, ...) have certain "classic" benchmark instances that are used heavily in the literature to compare the numerical strength of optimisation algorithms.

While this increases comparability of different algorithms, it also increases the danger of tailoring the algorithms (subconsciously, often) to the benchmark instances. A read a lot of hub location papers, and most of them test on the Australian post data (besides a few other sets, like the CAB set). This means that you cannot know whether the numerical results would still hold on instances with a different structure.

What can be done to solve this problem? I am looking for approaches from the literature that try to reduce this "overfitting" problem.

To make this clear: This is not meant as a rant or open discussion, but as a question for concrete, usable approaches.

Answer 1

To complement Michael's answer, which I think made the main points already:

First, an obvious strategy is to separate the data set used for testing and tuning, from the data set that are used in validation, which is a common practice in other areas (e.g. machine learning).

Second, since one can be never sure to avoid a bias, I think it is helpful to state all assumption on the data set and publish as much information as possible on it, to make it possible investigate a possible bias in later research. Here I find the recommendations in Good laboratory practice for optimization research helpful, in particular

• R.3: use, when possible, real-world data
• R.4: publish the data set in a central location
• R.5: make data set subject to peer review
• R.9: define statistical procedures for comparisons
• R.10: state the suggested computation times and number of evaluations
• R.11: present a range of different benchmark instances, covering different sizes and complexity

Finally, tuning algorithms for a certain instance structure may not necessarily be bad, portfolio algorithms are an example which exploit this. Indeed, more research, like for example Kate Smith-Miles work, into what makes instances hard could be useful.

Answer 2

Let me add a couple of things based on my experience. I created/collated the DIMACS instances for clique and coloring way back in 1992 and they are still used extensively, primarily for graph coloring. I also have kept track of results for a sports scheduling problem, the Traveling Tournament Problem, at http://mat.tepper.cmu.edu/TOURN A couple things I learned:

1) Don't let the literature get hung up on speed. For the DIMACS Challenge, we had programs to benchmark machines to allow for normalization of speeds, but there is a lot more to speed of a program than the speed of the underlying machine. Programmer skill, cache processes, random luck and far more play a role. At the end, I didn't trust any result about speed. It is far more interesting when new bounds are found or instance solutions are proven optimal. Code fine-tuning really doesn't come into play for that.

2) Benchmark libraries need to be alive and changing. The MIP people do a good job of this by creating new benchmark libraries every few years. I did that for the Traveling Tournament Problem, and I wish I had done that for the DIMACS instances. Again, fine tuning is less valuable when there are always new, more challenging, instances to solve.

I would note that "real world" doesn't always mean challenging. For the clique and coloring problems, practically every "real-world" instance we found had a large, completely obvious, clique that defined both the clique and the coloring. But it is important to keep checking that by constantly adding instances.

Answer 3

There are multiple aspects to this topic.

What can be done by testset compilers to prevent finetuning?

For one, testset creators are usually not including many very similar problems into the benchmark. For example, MIPLIB2017 was specifically compiled in a way to ensure diversity.

The design paper for the CEC2018 benchmarks specifically states:

The 15 benchmark problems are with diverse properties which cover a good representation of various real-world scenarios, such as being multimodal, disconnected,degenerate, and/or nonseparable, and having an irregular Pareto front shape, a complex Paretoset or a large number of decision variables [...]. Our aim is to promote the research of many-objective optimization via suggesting a set of benchmark functions with a good representation of various real-world scenarios

In one or more of the CEC challenges, all benchmark functions had some random components to them (scaling, rotation, ...) to prevent finetuning.

What can be done as a algorithm designer to ensure I am not biased towards certain implicit structure in the testset?

The biggest pitfall in my opinion is NOT relying on testsets: often researchers will create random instances to test their algorithm. These however usually have a lot more structure than one might think.

Make sure to select a testset that does not just include one type of instances.

Is your software designed to solve general traveling salesman instances? Make sure the testset includes both symmetric and asymmetric instances.

Are you designing a convex quadratic programming solver? Make sure the testset has both sparse and dense instances, ill-conditioned matrices, non-trivial Eigenvalue structure, etc.

Make sure your algorithm makes no assumption about special cases.