>   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

[CSPLib #]

Go to the CSPLib page for this problem

Problem description

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}.

Problem input

  • n, the number of pitch classes

Search space

The set of permutations of integer range [0..n-1]

Constraints

  • C1: Each pitch class occurs exactly once
  • C2: Differences between neighbouring notes are all different

Problem specifications

SpecificationOPLDLVLPARSE
BASE: Base specification
View
View
View
SBSO: Symmetry-breaking by selective ordering
View
View
View
AUX: Addition of auxiliary predicates
View
View
View
GCAD: Exploitation of alldifferent() global constraint
View
----
AUX-SBSO: Addition of auxiliary predicates plus Symmetry-breaking by selective ordering
View
View
View
AUX-SBSO-GCAD: Addition of auxiliary predicates plus Symmetry-breaking by selective ordering plus Exploitation of alldifferent() global constraint
View
----

Return to the problem list


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