The CLASSES 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 2.0.13.
There will be some restrictions on the problems tested in 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. this is forbidden:

    array[1..3] of set of 1..3: a = [{1,2}, {3}, {1,3}]; var 1..3: i; constraint card(a[i]) > 1; 

3. In order to facilitate local search entrants, ideally a model should wrap symmetry breaking constraints in a predicate “symmetry_breaking_constraint” e.g.,

    var 0..100: x; var 0..100: y; constraint x + y < 144; constraint symmetry_breaking_constraint(x <= y); 

   and redundant constraints in a predicate “redundant_constraint”, e.g.,

    array[1..4] of var 0..20: start; array[1..4] of int: duration = [3, 4, 6, 7]; array[1..4] of int: usage = [6, 3, 5, 3]; constraint cumulative(start, duration, usage, 10); constraint redundant_constraint(start[1] + dur[1] <= start[3] \/ start[3] + dur[3] <= start[1]); 

4. 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. For example,

    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_min, complete) satisfy; 

   is correct but not

    solve :: int_search([x,z], input_order, indomain_min, complete) satisfy; 

   even though most FD solvers would know the second was satisfiable.
5. Search annotations will be restricted to bool_search, int_search and seq_search.
   For bool_search and int_search only the following parameters (where applicable) will be used:
   • 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 value)
   • 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: objective; constraint x > 1 -> objective > 7; constraint x = 1 -> objective < 3; solve :: int_search([x, objective], first_fail, indomain_min, complete) maximize objective; 

   will first label x = 1 and find maximum value objective = 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 objective :: 8..10 and this time objective will be selected as the next variable to label. A full specification of the available choices is given in the FlatZinc 1.6 specification.
6. The objective variable must be called objective in optimisation problems, e.g. see previous example.

Output Requirements

Output from entries must conform to the FlatZinc 1.6 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.

Execution Environment

During the MiniZinc Challenge 2016 all VMs will run on machines with the following specification:

• Operating System: Ubuntu 14.04.4 LTS
• Processor(s): i7 3770 @ 3.40GHz (8 logical cores)
• Memory: 16 Gb
• VirtualBox 5.0.20r106931

Except in the Parallel searchi, Local search, and Open class, only a single core of one processor will be used for each entrant.

Benchmark Selection

The benchmarks for MiniZinc Challenge 2016 (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:

• 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 2.0.13 models, making use of only the global constraints included in the MiniZinc 2.0.13 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.

Initial Submission Round

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

The challenge will require solvers to process 100 MiniZinc models with a run-time limit of 20 minutes (process time) per problem.
NOTE that the MiniZinc to FlatZinc/XML-FlatZinc time will be included in this time.

Assessment

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

• timeUsed(p,s) - the wall clock time used by the solver, or timeLimit(p) if it was still running at the timeLimit (quantized to seconds).
• 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) assuming maximization
• optimal(p,s) - whether the objective value is proved optimal by the solver.

Scoring Procedure

• If s gives a better answer than s' it scores 1 point.
• If s and s' gives indistinguishable answers then scoring is based on execution time comparison (see below).
• If s gives a worse answer than s' it scores 0 point.

SATISFACTION PROBLEM

• solved(p,s) && not solved(p,s')

OPTIMIZATION PROBLEM

• solved(p,s) && not solved(p,s'), or
• optimal(p,s) && not optimal(p,s'), or
• quality(p,s) > quality(p,s'), or

CLASSES

The scoring calculations will be done once for each run class: FD search, Free search, Parallel search, Open class, and Local search. Note that if too few solvers are entered in a class then the challenge won't be run for that class.

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 solvers with the highest scores in each of the run classes: FD search, Free search, Parallel search, Open class, and Local search. The organizers may also award prizes to the best solvers on a particular category of problems. Note that if too few solvers are entered in a class then the challenge won't be run for that class and no prizes will be awarded for that class.

Restrictions

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. In addition, the organizers reserve the right not to run the challenge on classes with insufficient number of solver entrants.

Return to the MiniZinc Challenge 2016 home page.