Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Detecting and Breaking Symmetries by Reasoning on Problem Specifications
Ist Teil von
Abstraction, Reformulation and Approximation, 2005, p.165-181
Ort / Verlag
Berlin, Heidelberg: Springer Berlin Heidelberg
Erscheinungsjahr
2005
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
In this paper we address the problem of detecting and breaking symmetries in combinatorial problems, following the approach of imposing additional symmetry-breaking constraints. Differently from other works in the literature, we attack the problem at the specification level. In fact, many symmetries depend on the structure of the problem, and not on the particular input instance. Hence, they can be easily detected by reasoning on the specification, and appropriate symmetry-breaking formulae generated. We give formal definitions of symmetries and symmetry-breaking formulae on specifications written in existential second-order logic, clarifying the new definitions on some specifications: Graph 3-coloring, Social golfer, and Protein folding problems. Finally, we show experimentally that, applying this technique, even if in a naive way, to specifications written in state-of-the-art languages, e.g., opl, may greatly improve search efficiency.