>   Computer Science Department   >   Toni Mancini
[login|signup]      [Italiano|English]

Evaluating ASP and commercial solvers on the CSPLib

Toni Mancini, Davide Micaletto, Fabio Patrizi, Marco Cadoli
Dipartimento di Informatica e Sistemistica
Università di Roma "La Sapienza"
via Salaria 113, I-00198 Roma, Italy

Appeared in Constraints, 13(4), pages 407-436, 2008.

Web appendix

Modelling languages and solvers used

We present the output of our modelling task on 9 problems from the CSPLib in the following languages:

Problems considered

[CSPLib #] (details »)

Given a positive integer 'n_marks', this problem amounts to put 'n_marks' marks on a ruler, in such a way that the n_marks(n_marks - 1)/2 distances among them are all different. The objective is to find the length of the shortest ruler that admits the positioning of 'n_marks' marks.

[CSPLib #] (details »)

Given the twelve standard pitch-classes (c, c#, d, ...), represented by numbers 0,1,...,11, this problem amounts to find a series in which each pitch-class occurs exactly once and in which the musical intervals between neighboring notes cover the full set of intervals from the minor second (1 semitone) to the major seventh (11 semitones). That is, for each of the intervals, there is a pair of neighboring pitch-classes in the series, between which this interval appears.

We consider a generalization of this problem in which the set of numbers is the range from 0 to n-1, for any given positive 'n'. In particular, given such 'n', the problem amounts to find a vector s = (s1, ..., sn) that is a permutation of {0, 1,..., n-1} and such that the interval vector v = (|s2 - s1|, |s3 - s2|, ..., |sn - s(n-1)|) is a permutation of {1, 2,..., n-1}.

[CSPLib #] (details »)

In a golf club there are 32 social golfers who play once a week in 8 groups of 4. The problem amounts to find a schedule for as many as possible weeks, such that no two golfers play in the same group more than once.

Here we consider the decisional version of the problem (wrt the number of weeks 'weeks'), where the number of players and the group size are given as input.

[CSPLib #] (details »)

The problem amounts to color the edges of a complete graph with n nodes using the minimum number of colors, in such a way that there is no monochromatic triangle in the graph, i.e. in any triangle at most two edges have the same color.

[CSPLib #] (details »)

This is a generalization of the CSPLib specification, which is as follows: Given an 8 pint bucket of water, and two empty buckets which can contain 5 and 3 pints respectively, the problem requires to divide the water into two by pouring water between buckets (that is, to end up with 4 pints in the 8 pint bucket, and 4 pints in the 5 pint bucket) in the smallest number of transfers.

The generalization consists in making the specification parametric with respect to the start and goal configurations, which are now inputs to the problem.

[CSPLib #] (details »)

An order 'n' magic square is a 'n' by 'n' matrix containing the numbers 1 to n2, with each row, column and main diagonal equal the same sum. Given a positive integer 'n', the problem amounts to find a 'n' order magic square.

[CSPLib #] (details »)

This is a generalization of the specification given in the CSPLib (which fixes the forthcoming value 'n' to 4). Given two sets of the numbers from 1 to n, the problem amounts to arrange the 2n numbers in the two sets into a single sequence in which the two 1's appear one number apart, the two 2's appear two numbers apart, the two 3's appear three numbers apart,... , and the two n's appear n numbers apart.

[CSPLib #] (details »)

Life is played on a squared board, considered to extend to infinity in all directions. Each square of the board is a cell, which at any time during the game is either alive or dead. A cell has eight neighbours. The configuration of live and dead cells at time t leads to a new configuration at time t + 1 according to the rules of the game:
  • If a cell has exactly three living neighbours at time t, it is alive at time t + 1;
  • If a cell has exactly two living neighbours at time t, it is in the same state at time t + 1 as it was at time t;
  • Otherwise, the cell is dead at time t + 1.
A stable pattern, or still-life, is not changed by these rules. Hence, every cell that has exactly three live neighbours is alive, and every cell that has fewer than two or more than three live neighbours is dead. (An empty board is a still-life, for instance.)

Given a positive integer n, the problem amounts to find the densest possible still-life pattern, i.e. the pattern with the largest number of live cells, that can be fitted into an n by n section of the board, with all the rest of the board dead.

[CSPLib #] (details »)

The problem amounts to find as large a set S of strings (words) of length 8 over the alphabet W = {A,C,G,T} with the following properties:

  1. Each word in S has 4 symbols from {C,G};
  2. Each pair of distinct words in S differ in at least 4 positions;
  3. Each pair of words x and y in S (where x and y may be identical) are such that R(x) and C(y) differ in at least 4 positions.

    Here, R(x1,...,x8) = x8,...,x1 is the reverse of x1,...,x8 and C(y1,...,y8) is the Watson-Crick complement of y1,...,y8, i.e. the word where each A is replaced by a T and vice versa and each C is replaced by a G and vice versa.

Here we consider a decisional version of the problem: given integer nbwords, the problem amounts to find a set of nbwords words with the above properties.

[This web site could never be realised without the sophisticated features of a pure text editor and the extreme power of 220V]