Software and Benchmarks for Round Robin Tournament Problems

This page provides access to benchmark problems that were created for a study of the so-called pairing constraint. Details of the study can by found in the pairing paper. The terminology used here is introduced in this paper. All citations in this page refer to its bibliography.

Groups of Benchmarks

The letter n stands for the number of teams. n is always even here, except for the ACC 1997/98 case, where n = 9. In all benchmarks, teams are numbered starting from 0. Therefore the teams range from 0 to n - 1. The benchmarks are grouped into four categories:
  1. ACC 1997/98: This is the benchmark problem presented by Nemhauser and Trick in [14] and described in detail in [7]. The problem is available from Michael Trick's homepage. See also Walser's work for benchmarking a local search solution on this problem. Group name: acc.
  2. Unconstrained round robin: Dense single round robin tournaments without further restrictions. Group name: roundrobin_unconstrained.
  3. Constrained round robin: Dense single round robin tournaments with explicit exclusion of opponents for teams and rounds. Group name: roundrobin_constrained.
  4. Constrained double round robin: Dense double round tournaments with explicit exclusion of opponents for teams and rounds. Group name: double_constrained.
  5. Constrained intermural tournaments: Dense single round robin tournaments with explicit exclusion of opponents for teams and rounds, and the fixing of home/away patterns in the following way: For teams i where i = 0 to (n-2) div 2 - 1, the only sequence of two homes is at position i*2 + 1 and i*2 + 2. For teams i where i = (n-1) div 2 to n-3, the only sequence of two aways is at position i*2-n+1 and i*2-n+1. Group name: intermural_constrained.
To each of the groups belongs a directory, containing benchmark files and result files of experiments. To get a listing of the directory, click on the group name in the above listing.

Benchmark Files: Excluding Opponents

The benchmarks 3 to 5 are constrained by excluding possible opponents for particular teams in particular rounds. The corresponding benchmark files are generated by the program benchmark_generator.oz. The benchmark files with ending .ben_t are given in the benchmark group directories above. The format is as follows: ### Benchmark for <GROUP> round robin tournaments ### ### (for documentation, see http://www.comp.nus.edu.sg/~henz/projects/pairing) ### Number of teams: <N> Number of times: <M> Fixings: exclude opponent <O> for team <T> in round <R> The file names indicate the number of teams and the number of exclusion constraints to drop from the end of the given list. For example, the benchmark problem intermural_constrained_12_neq_1.ben_t has 12 teams and the last constraint is dropped. If no constraint is dropped, there are no solutions.

Running Benchmarks

The benchmarks reported in the paper were run by the program benchmark.oz, using the auxiliary programs acc.oz, roundrobin.oz, intermural.oz, and multiple.oz, using the programming system Mozart 1.1.0 on a 256 MB 400MHz Pentium II PC running Linux.

The benchmarks are given using four different techniques:

The files ending with <name>.average_t give the average runtimes and number of Oz spaces used for five runs.

Remarks for Oz Users

The benchmarks and result files are also available as Oz pickles in the files ending with .ben (benchmarks), .average (average runtimes and spaces), .sol (solutions), and .sta (runtime and spaces for single runs). The files ending .sol (solutions) and .sta are only in the tar file below.

The propagation algorithms are implemented in the programs pairing_tony.hh / pairing_tony.cc for Pairing 1, pairing_sven.hh / pairing_sven.cc / narrower_pairing.hh / narrower_pairing.cc for Pairing 2, and distinctD.hh / distinctD.cc for arc-consistent all-different. All these algorithms use the LEDA library.

The Makefile may come in handy for people who want to reproduce the results. All files mentioned in this page can be downloaded as benchmark.tar.gz.

Martin Henz