17
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Can someone tell me why this is "primarily opinion based"? Isn't this a concrete problem? How should I rephrase the question to be more fitting? $\endgroup$ – J. Fabian Meier May 31 at 20:09
  • $\begingroup$ You know what the most heavily tested nonlinear optimization problem is? The Rosenbrock banana function en.wikipedia.org/wiki/Rosenbrock_function , which is a nonlinear least squares problem (a very special structure of objective function), with zero reisiduals at the optimum (optimal objective = 0), so it's not even representative for two variable nonlinear least squares problems. Anyhow, same deal as machine learning, overoptimization due to training and evaluating on the same data (models). Even honest people do this to an extent, let alone people trying to game the system. $\endgroup$ – Mark L. Stone May 31 at 20:42
  • 3
    $\begingroup$ Closing this question would be (edit, just happened, so is), pardon my language, you know what. Do the closers want this site to just be a compendium of solutions tr homework and exam problems? $\endgroup$ – Mark L. Stone May 31 at 20:45
  • 1
    $\begingroup$ @J.FabianMeier I'm also not sure on better wording here, but maybe to remove the "opinion-based" part of the question, you can edit the last sentence to be something like "I wonder if there are any references on how this issue is addressed elsewhere" or something of that nature. $\endgroup$ – EhsanK May 31 at 20:55
  • 1
    $\begingroup$ For the record, I voted to reopen before any edits were made.Rather than closing, folks could have left comments suggesting improvements to the question. Real O.R. is messy, not a cvoobook, so I think it's o.k. for the site to reflect that to some extent. $\endgroup$ – Mark L. Stone May 31 at 21:33
10
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.