| 1. |
|
|
| 2. |
- Flener, Pierre, et al.
(author)
-
Efficient structural symmetry breaking for constraint satisfaction problems
- 2007. - 1
-
In: Proceedings of the International Symmetry Conference, Edinburgh, UK.
-
Conference paper (peer-reviewed)abstract
- Symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value and variable interchangeability is tractable using dedicated search procedures or symmetry-breaking constraints that allow nogoods and their symmetrically equivalent solutions to be stored and checked efficiently.
|
|
| 3. |
|
|
| 4. |
- Flener, Pierre, et al.
(author)
-
Static and dynamic structural symmetry breaking
- 2006
-
In: Twelfth International Conference on Principles and Practice of Constraint Programming (CP'06). - Berlin, Heidelberg : Springer Berlin Heidelberg.
-
Conference paper (peer-reviewed)
|
|
| 5. |
- Flener, Pierre, et al.
(author)
-
Static and dynamic structural symmetry breaking
- 2009
-
In: Annals of Mathematics and Artificial Intelligence. - : Springer Science and Business Media LLC. - 1012-2443 .- 1573-7470. ; 57:1, s. 37-57
-
Journal article (peer-reviewed)
|
|
| 6. |
- Flener, Pierre, et al.
(author)
-
Static and Dynamic Structural Symmetry Breaking
- 2008
-
Reports (other academic/artistic)abstract
- We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.
|
|
