MiniZinc Challenge 2010 Results

Entrants

The entrants for this year (with their descriptions, when provided):

In addition the challenge organisers entered the following FlatZinc implementations:

  • Chuffed (description). A C++ FD solver using Lazy clause generation.
  • Fzntini. Translates to SAT, uses TiniSAT.
  • G12/FD. A Mercury FD solver (the G12 FlatZinc interpreter's default solver).
  • G12/CPLEX. Translates to MIP, uses CPLEX12.1.

As per the challenge rules, these entries are not eligible for prizes, but do modify the scoring results. Furthermore, entries in the FD search category (Gecode, JaCoP, Chuffed, G12/FD) were automatically included in the free search category, while entries in the free search category (Fzn2smt, Fzntini, SCIP, CPLEX and promoted FD entries) were automatically included in the parallel search category. In that sense the "moral victory" probably goes to Gecode?

Summary of Results

The results for the MiniZinc Challenge 2010 were
  • Fixed search:
    • Gold medal: Gecode
    • Silver medal: JaCoP
  • Free search:
    • Gold medal: Gecode
    • Silver medal: fzn2smt
    • Bronze medal: JaCoP
  • Parallel search:
    • Gold medal (equal): Gecode + fzn2smt
    • Bronze medal: JaCoP

The results for parallel search were a bit surprising since Gecode-parallel is better than Gecode-free, and fzn2smt is the same in both categories. This results from the fact that Chuffed-parallel is worse than Chuffed-free and hence the purse scoring system gives points back to fzn2smt.

Results Presentation

The slides for the presentation of the results at CP2010 are here in Powerpoint and PDF

Description of Results

Times are in seconds.

If a promoted entry does not recognize an option (or states that it is just ignored), times and solutions from the previous category are used for scoring. The suffixes _fd, _free, and _parallel at the end of the solvers names indicates which actual configuration the solvers were run with.

There are 100 points for each problem instance.

mzn2fzn was run with the same time and memory limits as the solvers.

In the Status column:

  • S indicates a solution was found;
  • C indicates a complete search;
  • U indicates an unknown answer (as indicated by the solver or a time-out);
  • FE indicates an error during flattening (time outs, memory exhaustion, ...);
  • E indicates an runtime error while solving the problem;
  • I indicates an incorrect answer.

Incorrect answers:

  • jacop returns incorrectly unsatisfiable on the ghoulomb instances.
  • jacop returns "better than optimal" solutions on some depot-placement instances.
  • scip returns immediately and incorrectly unsatisfiable on filters (this behavior is observed whenever scip is provided with an incorrect fzn file however other solvers were able to parse the fzn generated for scip).

Errors:

  • cplex and scip abort during flattening on wwtp while trying to get bounds on unbounded int variables.
  • cplex and scip abort during flattening on solbat with a segmentation fault.
  • cplex abort during flattening with time-outs or memory exhaustion on ghoulomb and rcpsp_max
  • fzn2smt_free abort abort on bacp-16, ghoulomb and rcpsp_max with an out of memory Java exception.
  • Unknown answers from fzntini_free on ghoulomb and rcpsp_max instances were mostly due to memory alloc errors, probably due to memory exhaustion.

Selection:

Select a list of solvers and benchmarks and click on "Compute Results" to score the solvers against each other on the selected benchmarks. The entrants for each of the fd search, free search and parallel search categories can be selected with the corresponding buttons.

Solver selection: Problem selection:

Summary:

| Solver | Time | Score

Total per problem:

| Problem | Solver | Time | Score

Individual results:

| Problem | Instance | Solver | Status | Time | Objective | Score

Global constraint per model

The following table lists the global constraints used by each model in this year's challenge.

Model Global constraints used
bacp
costas-array alldifferent
depot-placement alldifferent
filters diffn, maximum
ghoulomb cumulative
grid-colouring
rcpsp-max cumulative
solbat
sugiyama alldifferent
wwtp_random
wwtp_real

The files on this page are for MiniZinc version 1.1.