[Coin-discuss] Benchmark Instances & code for format conversions

[Tobias Achterberg]

Dear Anureet,

I am one of the maintainers of MIPLIB 2003 (http://miplib.zib.de) and
can briefly summarize our experiences with collecting data.

I think, there are essentially two approaches for creating a test
suite of problem instances:
1. Collect everything you get (probably sort them by problem class)
and put them on a website. The goal is to provide a large variety of
instances from which everyone can extract their own test suite.
2. Carefully select a reasonable subset of available instances in
order to provide a widely accepted test suite (for a particular
domain) that everyone conducting experiments in this domain can use in
their papers.

The advantage of (1) is that with a large number of instances, it
should be possible to extract a reasonable subset for many different
computational studies, i.e., the usability of the instance library is
quite high.
The advantage of (2) is that authors can much easier compare their
results to the ones of other papers because everyone (in this
particular domain) uses the same instances.

MIPLIB was and still is clearly focused on the 2nd approach, providing
a library of test instances for general mixed integer programming. We
spent some effort to convert the instances into a standard format
(this is by far not trivial, since many instances do not meet the
standard MPS file format) and to provide tables with statistics on the
instances.
As maintainers of the MIPLIB, we essentially faced the following
situation:
- We can only spend a finite time to maintain the library, since all
of us have to work on projects and always have to meet the next deadline.
- Many colleagues throughout the world had nice ideas how a library
like the MIPLIB should be assembled, which criteria one should impose
on the individual instances and on the test set as a whole, and how
maintanance should be organized.
- Only a small number of people contributed problem instances to the
library. The reason might be that we wanted to collect real-world or
close-to-real-world instances from industry projects, but most of the
commercial companies are highly paranoid when it comes to publishing data.
- It is VERY hard (probably impossible) to create a test suite that
represents an unbiased sample of challenging real-world instances.


In order to also address approach (1), we included a "contributed"
section on the MIPLIB website (http://miplib.zib.de/contrib/) where we
just collect instances that were contributed. No effort is spent on
converting them to a standard file format, extracting statistics, or
assembling reasonable test suites.

We do not want to maintain copies of instances that are available in
other collections at other websites. Such a "grab everything you can
get from any sources" approach bears the high risk that an instance
can be found under the same name in different sources, and that the
different versions are in fact NOT equal (for example, due to wrong
floating point number treatment during file format conversion).


> 1. Maintaining benchmarks in usable format and making them publicly
> available is a difficult task. Here is a reply I got from an author
> after requesting for benchmark instances which were used in his 2003 paper
>  
> "....Regarding the instances, I regret to say that they are lost, after
> moving so much. ..."

I would say, this reason should be the exception. The usual reason is
that authors are not allowed (by their industry partners) to publish
their data.


> 3. Many a times people use random instances for their experiments.
> Unless the experiment is repeated with precisely those instances, it is
> very difficult to accurately gauge the impact of any new idea. (And of
> course there is an implementation effort involved in reproducing those
> instances, see (2) above).

I saw a lot of researchers that make their random instances available
on their websites. I think if there are no restrictions by industry
partners, everyone should publish the instances on which computational
studies were conducted. Otherwise, the computational results will lose
most of their value.


> To summarize, availability of benchmark instances in "appropriate
> format" is an equally important aspect of computational OR as is the
> availability of the code. In my opinion, maintaining benchmark instances
> and "format conversion codes" along with the implementation code would
> greatly enhance the scope and reach of COIN-OR.

I totally agree. But please keep in mind that this is a non-trivial
task. Just creating a website where everyone can upload instances is
by far not enough. You will have to actively collect instances, make
sure that you give credit to the original source, if file format
conversion has to be applied you have to indicate this and give the
instance a different name, ....


Best,   Tobias

-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany