11th DIMACS Implementation Challenge


Competition

As in previous challenges, we had a friendly competition between participants. The exact details were worked out with the help of all participants using our mailing list (which is still active).

Rules and Scripts

The precise competition rules are available as PDF files:

We ask all participants to take a careful look at the latest version. If you find any issues or have suggestions for improvement, please use the mailing list to let us know.

The scripts for the contest are also available:

Note that this file does not include the test instances, which should be downloaded separately and saved to the appropriate subfolder of instances (created when unpacking the file above). Tentative lists of test instances are available in the file again. The list may change as we get more input from the mailing list.

For convenience, we have compiled the list of test instances for six variants (as gzipped tar files):

These instances are subsets of those available on the downloads page, with some minor fixes in the COMMENT section.

Results

The third phase (the official one) of the competition included algorithms from various groups:

  • AB: Ernst Althaus and Markus Blumenstock
  • fscipjack/scipjack: Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt and Yuji Shinano
  • heinz: Mohammed El-Kebir and Gunnar W. Klau
  • KTS: Zhanghua Fu and Jin-Kao Hao
  • mozart*/staynerd: Matteo Fischetti, Markus Leitner, Ivana Ljubic, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin and Markus Sinnl
  • polito: Indaco Biazzo, Anna Muntoni, Alfredo Braunstein and Riccardo Zecchina
  • PUW: Thomas Pajor, Eduardo Uchoa and Renato Werneck
  • schmidt: Chinmay Hegde, Piotr Indyk and Ludwig Schmidt
  • stephop: Oleg Burdakov, Jonas Kvarnstrom and Patrick Doherty
  • viennaNodehopper: Markus Sinnl and Ivana Ljubic

The results for all variants for which there were enough participants can be found here:

Recall that the first two phases are warm-ups only; the third phase is the official one. There were submissions by 12 groups to the first phase, most of which having results for multiple variants. Six variants had submissions by at least two groups: DCST, MWCS, PCSPG, RPCST, SPG, and STPRBH. There will be a formal competition for these six variants. The results of these submissions, compiled by the ZIB team, are available here. Since submissions to this phase could use different sets of instances and time limits, the results were not necessarily comparable.

Additional information

  • Problems. There will be a separate competition for each variant of the Steiner Tree problem that has at least two submissions to the challenge. Each competition will have at least two subcategories:

    • Pareto challenge: in this category, submissions are evaluated in terms of both solution quality and running times. The organizers will provide the appropriate means for ensuring that results are comparable.

    • Quality challenge: here the goal is to find the best possible solution, regardless of running time.

  • Workshop participation. The main goal of the challenge is to stimulate the exchange of ideas. With that in mind, to participate in the competition authors must also submit (and present) a paper at the workshop discussing their entry. For submissions with multiple authors, only one is required to attend the workshop, although wider participation is encouraged. A group may participate in multiple categories.

  • Voluntary participation. Participating in the competition is not mandatory. Researchers may present at the workshop without participating in the competition.

  • What to submit. Although not required, submitting source code is encouraged. The code will not be distributed, and only the organizers of the competition (and possibly their students) will have access to it. For those who prefer not to submit the code, submission of an executable (binaries) will be required. Also keep in mind the item below.

  • The book. 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). Be aware that the source code is required as part of the MPC reviewing process. Note that participation in the competition is not a requirement for invitation to submit to the special issue of MPC; conversely, submitting to MPC is not mandatory even for those who participate in the competition. (In particular, work already published in another journal may be presented at the challenge, but may not be eligible to appear in MPC.)

  • Testing. The experiments will be conducted at the Zuse Institute Berlin (ZIB) under the supervision of Thorsten Koch. The machines used for testing have x86 processors and run Ubuntu 14.04 LTS, with standard tools and libraries (including GCC, CPLEX, Gurobi, OpenMP, LEMON, OGDF). If there is a specific tool/library you need, please contact the organizers directly or using the mailing list.

  • Instances. The set of instances tested for the competition will be defined by the organizers. To avoid overfitting, some of the instances may not be revealed before the submission deadline.

  • Parallelism. We plan to have competitions for sequential code as well as multicore (shared memory) variants. Each machine tested will most likely have 2 sockets with 10 cores each (final confirmation will be given before the deadline). We may consider distributed implementations (on more than one machine) if there is enough demand; please contact the organizers if you have a strong desire for a distributed category.

  • When to submit. See the PDF file above for deadlines.

  • What to report. Papers submitted to the workshop are encouraged to give as much detail as possible about their results to ensure reproducibility. There will be a (generous) page limit for the main text, and an appendix with detailed results is encouraged. These papers will be published online only, and will not be fully refereed. The MPC submission, for those invited, will go through MPC's usual review process.

This is a rough framework and is subject to change. Potential participants are invited to discuss these rules using our mailing list.