Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 235 - 273 |
| Number of pages | 39 |
| Journal | Constraints |
| Volume | 20 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2015 |
Cite this
}
A method for detecting symmetries in constraint models and its generalisation. / Mears, Christopher David; Garcia De La Banda, Maria Jose; Wallace, Mark; Demoen, Bart.
In: Constraints, Vol. 20, No. 2, 2015, p. 235 - 273.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - A method for detecting symmetries in constraint models and its generalisation
AU - Mears, Christopher David
AU - Garcia De La Banda, Maria Jose
AU - Wallace, Mark
AU - Demoen, Bart
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://goo.gl/alBov3
U2 - 10.1007/s10601-014-9175-5
DO - 10.1007/s10601-014-9175-5
M3 - Article
VL - 20
SP - 235
EP - 273
JO - Constraints
JF - Constraints
SN - 1383-7133
IS - 2
ER -