Results for the 2024 MiniZinc Challenge have now been announced!

MiniZinc Challenge 2008 -- Rules

These are the official rules for the MiniZinc Challenge 2008. Version 1.2
These rules were last updated on 16 June 2008.

Entrants

The MiniZinc Challenge 2008 will test solvers on problems written in MiniZinc 0.8.
Let name be the name of the solver system in what follows.

An entrant in the challenge is a constraint solver submitted in either source code or binary format.

Binary format submissions must be compatible with the competition hardware and operating system.
Entries implemented in Java should provide a Java archive, i.e. a .jar file, plus a shell script that invokes the solver. Non-Java entries may also be invoked via a shell script.

Each entrant must provide a gzipped tarball containing the following:

  1. a README file explaining how to (compile and) install the solver.
  2. a text file named DESCRIPTION, that contains a short (1-2 pages) description of the system. This should include a list of all authors of the system and their present institutional affiliations. It should also describe any algorithms or data structures that are not standardly used in such systems. System descriptions will be posted on the MiniZinc Challenge 2008 website.
  3. name -- a FlatZinc solver executable handling FlatZinc version 0.8 and other built-in predicates specific to the solver.
  4. name.mzn -- a definition of the globals in globals.mzn specialised for the solver name, e.g. by re-defining existing predicates as builtin-ins. Entries should not add new global constraints or delete existing ones.
    The name.mzn file may just be the globals.mzn available from the competition website.
  5. any other shell scripts, executables, Java archives etc required by the solver.

Installation and execution of solvers must not require root access.
Binaries should be statically linked.

The organizers will make reasonable efforts to install each system, including communication with the submitters of the system in case of difficulties. Nevertheless, the organizers reserve the right to reject an entrant if its compilation or installation process proves overly difficult.

The results will be announced at CP2008. Entrants are encouraged to physically attend CP2008, but are not required to in order to participate or win.

There will be two competition CLASSES:

  • FD search: solvers in this class must follow the search strategy defined in the problem, they will be disqualified if there is evidence that they do not follow the search strategy.
  • Free search: solvers in this class are free to ignore the search strategy. All FD search solvers will be automatically entered in this class too.

The README file included in the entry must specify which competition CLASS(es) the entry is to be entered in.

Problem Format

The problem format will be MiniZinc 0.8.
There will be some restrictions on the problems tested in this first instance of the MiniZinc Challenge.

  1. No floats may be involved in any model. This is to avoid accuracy differences and simplify entry requirements.
  2. No variable sets of integers may be used in any model. This is to simplify entry requirements. Not even implicit var sets of int, e.g. 
     array[1..3] of set of 1..3: a = [{1,2}, {3}, {1,3}]; var 1..3: i; constraint card(a[i]) > 1;
  3. Each solve item must be annotated with a search strategy, such that fixing all the variables appearing in the search strategy would allow a value propagation solver to check a solution. e.g. 
     var 1..5:x; var 1..5:y; var 1..5:z; constraint x <= y /\ y <= z; solve :: int_search([x,y,z], "input_order", "indomain", "complete") satisfy;
    is correct but not 
     solve :: int_search([x,z], "input_order", "indomain", "complete") satisfy;
    even though most FD solvers would know the second was satisfiable.
  4. Search annotations will only use a restricted class of things, to simplify entry requirements.
    • variable choice:
      • input_order
      • first_fail (variable with smallest domain size)
      • anti_first_fail (variable with largest domain size)
      • smallest (variable with smallest minimal value)
      • largest (variable with largest maximum element)
    • value choice: [examples for domain {1,3,4,18}]
      • indomain_min (x <= 1; x > 1)
      • indomain_max (x >= 18; x < 18)
      • indomain_median (x = 3 ; x != 3)
      • indomain_split (x <= (1+18)/2 ; x > (1+18)/2 )
      • indomain_reverse_split (x > (1+18)/2 ; x <= (1+18)/2 )
    • search style
      • complete
    Note that for variable choices ties are broken by taking the earliest variable in the given array. Also note that the decision is reassessed at each choice 
     var 1..5: x; var 1..10: y; constraint x > 1 -> y > 7; constraint x = 1 -> y < 3; solve :: int_search([x,y],"first_fail","indomain_min","complete") maximize y;
    will first label x = 1 and find maximum value y = 2 eventually on backtracking to the choice x = 1, then setting x >= 2 in most FD solvers will have domains for x :: 2..5 and y :: 8..10 and this time y will be selected as the next variable to label. A full specification of the available choices is given in the FlatZinc 0.8 specification.
  5. Each model will have an output item, which constructs a MiniZinc data file for the original model, giving at least the variables appearing in the search annotation. 
     var 1..5: x; var 1..5: y; constraint x < y; solve :: int_search([x,y],"input_order","indomain","complete") satisfy; output ["x = ",show(x),"\ny = ",show(y),"\n"];
    For optimization problems the output will also show the objective function of the solution. 
     var -5..5: z = x - y; solve :: int_search([x,y],"input_order","indomain","complete") maximize z; output ["%% OBJ = ",show(z),"\nx = ",show(x),"\ny = ",show(y),"\n"];

Output Requirements

The FlatZinc 0.8 executable should output as follows:

For satisfaction the first solution found should be output using the output item. Note that in the FD search class, the first solution found is important for judging correctness of the search. If the problem is proved unsatisfiable then a single line

 No solution found.

should be output.

For optimization some non standard output is required. The solver is free to output any solution via the output item of the model that it finds. It should only output solutions in increasing order of optimality. For the FD search class, the solutions must be output in the order found by the search procedure. The evaluation will use the last output solution. If the problem is proved unsatisfiable then a single line

 No solution found

should be output. If the optimal solution is found, then after it is printed using the output item a single line

 Optimal solution found

should be output.

Note that all output must be to the standard output.

Execution Environment

During the Minizinc Challenge 2008 all programs will run on machines with the following specification:

  • Operating System: Debian GNU/Linux 4
  • Processor(s): 3.4Ghz Intel Pentuim D (dual core)
  • Memory: 4 Gb
  • Cache: 2Mb L2 cache
  • C compilers: gcc 3.4.6, 4.1.2, Java 1.5
  • Shells: bash 3.1, tcsh 6.14, zsh 4.3,

If your system requires other compilers or tools please contact us and we will try to make them available.

The above machines support both 32- and 64-bit environments. Binaries may be compiled for either.

Only one core of one processor will be used for each entrant.

Benchmark Selection

The benchmarks for MiniZinc Challenge 2008 (as well as for the qualification rounds) will be selected by the organizers to try to examine some of the breadth of characteristics of FD solvers.

  • propagation speed
  • search speed
  • global constraints
  • satisfaction
  • optimization

To obtain benchmarks of suitable difficulty we will select only such instances that can be solved by at least one of the participating solvers in a sensible time-frame. For the qualification rounds no such restriction applies.

In order to collect good benchmarks each entrant is strongly encouraged to submit one or two MiniZinc 0.8 models, making use of only the globals defined in globals.mzn in that distribution, as well as some (preferably 10) instance files for each model. The instances should range from easy to hard if possible. Note that the model must conform to the problem format restrictions above.

Submitted benchmarks must be placed in the public domain.

Qualification Rounds

There will be two qualification rounds. Successful participation (i.e. no incorrect results; compliance with I/O format requirements; sufficient performance) in at least one of them is mandatory to qualify for the MiniZinc Challenge 2008.

The Challenge

The challenge will be require solvers to process 100 Minizinc models with a run-time limit of 15 minutes (process time) per problem. The MiniZinc to FlatZinc conversion time will not be included in this, but the organizers reserve the right to penalize entries that use massively complicated globals.mzn libraries to reduce solving time.

Assessment

Each solver s is run on problem p and the following information is collected.

  • timeUsed(p,s) - the time used by the solver, or timeLimit(p) if it was still running at the timeLimit.
  • solved(p,s) - true if a correct solution is returned, or correct unsatisfiability is detected
  • quality(p,s) - the objective value of the best solution found by the solver (that is the last solution fully output before the time limit)
  • optimal(p,s) - whether the objective value is proved optimal by the solver.

Each problem will come with a identical total points purse totalPurse which we assume is 2000 points which will be divided among entries as follows (this is adapted from the SAT 2005 and SAT 2007 contests).
If no solver solves the problem then the purse is not distributed.

SATISFACTION PROBLEM

The totalPurse is split 50/50 into solutionPurse for solution purse and speedPurse points for speed purse.

 solutionPurse = totalPurse / 2 speedPurse = totalPurse / 2

The solutionPurse is divided equally among all solvers returning a correct solution within the time limit.

 solutionAward(p,s) = solutionPurse / number of solvers solving problem p

The speed purse is divided as follows. Each solver s is given a speed factor for each problem p. Times are in seconds.

 speedFactor(p,s) = timeLimit(p) / (1 + timeUsed(p,s))

or 0 if solver s did not solve p.

 speedAward(p,s) = speedPurse * speedFactor(p,s) / sum_s(speedFactor(p,s))

OPTIMIZATION PROBLEM

The purse is dynamically split between solution quality and speed.

Let S be the number of solvers solving the problem within the time limit.
Let O be the number of solvers returning the best objective value of any solver.
Note that this may not be the optimum, but if one solver finds and proves the optimal, then O is only the solvers that find and prove an optimal solution.

The total purse is split as follows:

 qualityPurse = totalPurse * S / (O + S) speedPurse = totalPurse * O / (O + S)

Note if every solver find the optimal then the purse is split equally. The rationale behind the splitting is that unless proving optimality a solver should keep trying until the time limit.

The speed purse is split between solvers that return a best solution (and prove optimality if at least one such solver did) as for satisfaction problems.

The qualityPurse is split as follows: Let B(p) be the largest best solution found by any solver and W(p) the smallest best solution found by any solver.
If B(p) = W(p)o the points are split equally amongst solvers that found a solution.
Otherwise, we interpolate on a line from the best solution B(p) to the W(p) - (B(p) - W(p)) that is the solution twice the distance from the best to the worst solution.

 qualityFactor(p,s) = solution(p,s) - (2 * W(p) - B(p))

or 0 if the solver s did not solve p

 qualityAward(p,s) = qualityPurse * qualityFactor / sum_s(qualityFactor(p,s))

The rationale behind this splitting is that some of the quality points are given for achieving a solution, while the remainder are split on relative quality of solution.

CLASSES

The scoring calculations will be done once for each class: FD search and Free search.

The organizers may well run entrants in the FD search class on a series of smaller problems to test that they indeed are following the given search strategy. These problems will not accrue points, but may disqualify an entry from the FD search class.

Prizes

The solvers will be ranked on total points awarded. There will be prizes for the three solvers with the highest scores in each of the classes: FD search and Free search. The organizers may also award prizes to the best solvers on a particular category of problems.

Restrictions

Due to limited computational resources, the organizers reserve the right not to accept more than one version of a particular solver (defined as sharing 50% of the source code). The organizers reserve the right to enter their own systems--or other systems of interest--to the competition, but these will not be eligible for prizes, but still will modify the scoring results.