SODA

Compositional derivation of symmetries for constraint satisfaction

Van Hentenryck, Pascal and Flener, Pierre and Pearson, Justin and Ågren, Magnus (2005) Compositional derivation of symmetries for constraint satisfaction. In: Proceedings of SARA'05, 26-29, 2005, Edinburgh, UK.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/11527862_17

Abstract

This paper reconsiders the problems of discovering symmetries in constraint satisfaction problems (CSPs). It proposes a compositional approach which derives symmetries of the applications from primitive constraints. The key insight is the recognition of the special role of global constraints in symmetry detection. Once the symmetries of global constraints are available, it often becomes much easier to derive symmetries compositionally and efficiently. The paper demonstrates the potential of this approach by studying several classes of value and variable symmetries and applying the resulting techniques to two non-trivial applications. The paper also discusses the potential of reformulations and high-level modeling abstractions to strengthen symmetry discovery.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Springer LNCS: 3607
ID Code:3681
Deposited By:Magnus Ņgren
Deposited On:12 Oct 2009
Last Modified:18 Nov 2009 16:25

Repository Staff Only: item control page