These are the official rules for the MiniZinc Challenge 2009.
Version 1.0.
These rules were last updated on 1 June 2009.
The MiniZinc Challenge 2009 will test solvers on problems written in
MiniZinc 1.0.
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.
Constraint solvers that have several variants, for example that can alternatively
use copying or trailing, may submit one entry per variant although the organizers
reserve the right to reject such variations if they not sufficiently interesting,
(e.g. multiple copies of the same solver with differing parameters).
Binary format submissions must be compatible
with the competition hardware and operating system.
Each entrant must provide a gzipped tarball containing the following:
a README file explaining how to (compile and) install the solver.
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 2009 website.
fzn_name -- an executable file that invokes a FlatZinc solver handling FlatZinc
version 1.0 or XML-FlatZinc version 1.0
This executable will be invoked from the command line as follows:
fzn_name [<options>] file.fzn
The argument file.fzn is the name of a FlatZinc 1.0 model instance to evaluate.
The executable must support the following command line options:
a directory named globals containing any solver-specific definitions of the
global constraints in the MiniZinc library.
This directory may also contain a file named redefinitions.mzn that contains
redefinitions of FlatZinc built-ins 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 CP2009. Entrants are encouraged to physically attend CP2009, but are not required to in order to participate or win.
There will be two competition CLASSES:
There will also be an exhibition CLASS:
The exhibition class is for demonstration only; it does not count towards an entry's final result.
The README file included in the entry must specify which competition CLASS(es) the entry is to be entered in.
The problem format will be MiniZinc 1.0.
There will be some restrictions on the problems tested in MiniZinc challenge.
array[1..3] of set of 1..3: a = [{1,2}, {3}, {1,3}];
var 1..3: i;
constraint card(a[i]) > 1;
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.
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 1.0 specification.
var 1..5: x :: is_output;
var 1..5: y :: is_output;
constraint x < y;
solve :: int_search([x, y], input_order, indomain, complete)
satisfy;
For optimization problems the output will also show the objective function
of the solution. In all optimization problems the value of the objective
function will be given by a variable named objective.
var -5..5: x :: is_output;
var -5..5: y :: is_output;
var -5..5: objective :: is_output = x - y;
solve :: int_search([x, y], input_order, indomain, complete)
maximize objective;
Output from entries must conform to the FlatZinc 1.0 specification. For optimization problems, if the time limit is exceeded before the final solution is printed then the last complete approximate solution printed will be considered to be the solution for that entry. Note that is important that entries flush the output stream after printing each approximate solution.
During the MiniZinc Challenge 2009 all programs will run on machines with the following specification:
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.
The benchmarks for MiniZinc Challenge 2009 (as well as for the qualification rounds) will be selected by the judges to try to examine some of the breadth of characteristics of FD solvers:
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 1.0 models, making use of only the global constraints
included in the MiniZinc 1.0 library, as well as some (preferably 20)
instance files for each model.
The instances should range from easy (about a minute)
to hard (about 15 minutes) if possible.
Note that the model must conform to the problem format restrictions above.
Submitted benchmarks must be placed in the public domain.
There will be an initial submission round, which will provide the organizers with an opportunity to provide feedback on entries' compatibility with the competition hardware, compliance with the FlatZinc specification and any other matters that may arise. Submission in the initial round is not required in order to qualify for the final round, but it is strongly encouraged.
The challenge will 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 definitions in order to reduce solving time.
The conversion time from FlatZinc to XML-FlatZinc will also not be included.
Each solver s is run on problem p and the following information is collected.
Each problem will come with an 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.
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))
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 finds the optimum 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) 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.
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.
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.
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.
Return to the MiniZinc Challenge 2009 home page.