Formally, the challenge has several elements:

  1. An initial phase devoted to collecting and improving a set of benchmark instances.
  2. A second (somewhat overlapping) phase in which participants develop and evaluate their algorithms and implementations.
  3. A workshop in which participants present papers devoted to the challenge.
  4. A competition comparing implementations on a small set of representative instances, with results announced during the workshop.
  5. A (refereed) book (a special issue of Mathematical Programming Computation) dedicated to the best new research presented at the workshop.

This challenge is open to anyone who wishes to participate. Participation can take two forms:

  • Instances for algorithm evaluation. The instances should be natural and interesting. Instances stemming from real-world applications are especially welcome, as are synthetic instances that are particularly challenging for one or more algorithms.
  • Algorithm evaluation. Authors are encouraged to submit papers reporting on the implementation and experimental evaluation of particular algorithms. Papers should include results for the Challenge common testbed so that there is common ground for comparison. Algorithms that improve the state-of-the-art in practice are encouraged, as are other works of scientific merit. In particular, the experimental evaluation of algorithms with good theoretical guarantees is encouraged as well.

Participants may submit results for as many algorithms (and problems) as they wish. Although DIMACS Challenges usually focus on heuristics, we welcome any optimizers reporting results for the benchmarks, as this will provide an interesting perspective. Works on variants of the Steiner tree problem (including constraints found in practice) are encouraged.

Only papers presented at the workshop are eligible to participate in the competition or for submission to the book. Otherwise, participation is flexible. In particular:

  • You may contribute instances without presenting a related paper at (or even attending) the workshop, athough attendance is encouraged.
  • Authors are welcome to submit papers heavily based on work they have previously published elsewhere, as long as they are clearly marked as such. Such submissions are eligible for presentation at the workshop and for participation in the competition. They will not be considered for the book, however, which is restricted to papers with substantially new content.

Selected novel entries from the challenge will be invited to submit to a special issue of Mathematical Programming Computation (see also pages at ZIB and The Mathematical Programming Society). Submissions will be subject to the standard reviewing process at MPC (with their editors).

If you are considering participating in the Challenge, please contact us and let us know of your plans. Please do so even if you are not yet sure if you will participate. We have set up a mailing list to facilitate communication among participants and organizers.