Changes Compared to Previous Editions

This section describes the differences between the Fourth International Constraint Solver Competition (CSC'2009) and the Third International Constraint Solver Competition, which was organised in 2008.

CSC'2009 allows any kind of global constraints defined on integer variables. Since one of the goal of the competition is to accept any kind of solver, we don't expect each submitted solver to support all global constraints, or indeed all constraints.

Having solvers with different constraint handling capabilities, we need a mechanism to determine the constraints which the solvers can handle. To do this we introduce the notion of a solver's Boolean capability vector, capability vector for short, which consists of a sequence of ones and zeros acting as indicators of the constraints which the solver can handle. Solvers which have the same capability can be naturally compared. Solvers with different capabilities can be compared on instances which belong to the intersection of their capabilities, provided it is nonempty.

The first step in the competition is to collect the capabilities of each solver. To determine the solver's capability vector, we require that solver is capable of outputting a special answer `s UNSUPPORTED' whenever it reads a constraints which it cannot handle. This should be quite easy to implement in each solver. For example, it may be generated by a driver script which generates this output if the real solver fails to parse an instance.

Two solvers which have a nonempty capability vector intersection can be ranked on the basis of their results for instances belonging to the intersection of their capabilities. Solvers will be clustered according to their capabilities and a ranking will be established between solvers which support the same kinds of constraints. The goal of the competition is to produce all relevant ranking. However, there is potentially an exponential number of different capabilities and therefore an exponential number of rankings. To restrict this number, rankings will not be established when a cluster of solvers contains fewer than 3 solvers (with different authors) or when there are fewer than 20 instances specific to the cluster. Should the number of rankings still be too large, the organisers retain the right to ask the independent judges to select a limited number of relevant rankings to publish.

For example, let's assume that solvers $\mathit{BE}_i$ have support for only binary constraints in extension, solvers $\mathit{NG}_i$ have support for all constraints but global ones and solvers $\mathit{AD}_i$ have support for $\mathit{allDifferent}$ as well as any other kind of non global constraint. Let's further assume that a few other solvers have the same capabilities. The competition will produce a ranking for

• the cluster of solvers with support for $\mathit{allDifferent}$ as well as any other kind of non global constraint. This will gather solvers $\mathit{AD}_i$.
• the cluster of solvers with support for all constraints but global ones. It will compare solvers $AD_i$ and $NG_i$.
• the cluster of solvers with support for only binary constraints in extension. It will gather solvers $\mathit{AD}_i$, $\mathit{NG}_i$ and $\mathit{BE}_i$

In a cluster of solvers, a solver which would answer 's UNSUPPORTED' on even a single instance excludes itself from the ranking because it indicates that it doesn't have support for all kinds of constraints of the cluster. This solver will still appear in the sub clusters where it never answers 's UNSUPPORTED'.

If in a cluster of solvers, a solver gives an incorrect answer (UNSATISFIABLE on a satisfiable instance for example), it is reported as incorrect in this cluster and excluded from the ranking. This solver will still appear in the ranking of the sub clusters as long as it doesn't produce an incorrect answer.

All global constraints are allowed in the instances. However, if no instance with a given global constraint is submitted to the competition, this global constraint will be ignored. In other words, organisers will not ensure that any possible global constraint is used in the competition.

The following is the list of the 10 global constraints selected to give a direction to the contestants.

• $\mathit{allDifferent}$;
• $\mathit{cumulative}$;
• $\mathit{weightedSum}$;
• $\mathit{element}$;
• $\mathit{disjunctive}$;
• $\mathit{lexLess}$;
• $\mathit{lexLessEq}$;
• $\mathit{nValue}$;
• $\mathit{globalCardinalityWithCosts}$; and
• $\mathit{globalCardinality}$.