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

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.

Problem input

n, the number of graph nodes

Search space

The set of all possible assignments of colors to the graph nodes.

Objective function

Minimize the number of colors used

Constraints

C1: For any triple of different nodes, not all edges linking pairs of them have the same color

Problem specifications

Specification	OPL	DLV	LPARSE
BASE: Base specification	View	View	View
SBSA: Symmetry-breaking by selective assignment	View	--	View
SBLI: Symmetry-breaking by lowest index ordering	View	View	View
SBSB: Symmetry-breaking by size-based ordering	View	View	View
AUX: Addition of auxiliary predicates	View	View	View
AUX-SBLI: Addition of auxiliary predicates plus Symmetry-breaking by lowest index ordering	View	View	--
AUX-SBSB: Addition of auxiliary predicates plus Symmetry-breaking by size-based ordering	View	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]