Toni Mancini

Avvisi
23/4/2024	25 aprile: l'Italia ricorda la liberazione dall'occupazione nazista e dal regime fascista, simboleggiata dall'insurrezione del 25 aprile 1945 proclamata dai Partigiani. [Ultime lettere di condannati a morte e di deportati della Resistenza italiana] [Costituzione della Repubblica].

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

Problem input

n_marks, the requested number of marks to be positioned on the ruler
maxval, an upper bound of the ruler length

Search space

The set of all possible positionings of n_marks on the ruler, i.e., the set of all total functions from [1..n_marks] (marks) to [0..maxval] (positions)

Objective function

Minimize ruler length

Constraints

C1: First mark must be set to 0
C2: Distances between different marks must be all different
C3: Ruler mark values must be in ascending order

Problem specifications

Specification	OPL	DLV	LPARSE
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]