Title: A method for detecting symmetries in constraint models and its generalisation
Authors: Mears, Christopher ×
Garcia de la Banda, Maria
Wallace, Mark
Demoen, Bart #
Issue Date: 15-Apr-2015
Publisher: Kluwer
Series Title: Constraints vol:20 issue:2 pages:235-273
Article number: 1
Abstract: The symmetries that appear in many constraint problems can be used to significantly speed up the search for solutions to these problems. While the accurate detection of symmetries in instances of a given constraint problem is possible, current methods tend to be impractical for real-sized instances. On the other hand, methods capable of detecting properties for a problem model – and thus all its instances – are efficient but not accurate enough. This paper presents a new method for inferring symmetries in constraint satisfaction models that combines the high accuracy of instance-based methods with the efficiency of model-based methods; the key insight is that symmetries detected for small instances of the model can be generalised to the model itself. Experimental evaluation shows that this approach is able to find all symmetries in almost all the benchmark problems used. The generality of our method is then illustrated by showing how it can be applied to infer other properties.
ISSN: 1383-7133
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
art%3A10.1007%2Fs10601-014-9175-5.pdf Published 1243KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science