Hello,
I'm currently developing a solver for a problem using Gecode. Paradoxically, I
have not encountered any problem for modeling and search solution. However I'm
having trouble with symmetry breaking.
My problem is to place in a square array (n × n) elements respecting some
constraints. The peculiarity of my problem is that solutions are "toroidal". A
concrete example:
Suppose that this arrangement is a solution (here n = 4):
+---+---+---+---+
| a | b | c | d |
+---+---+---+---+
| e | f | g | h |
+---+---+---+---+
| i | j | k | l |
+---+---+---+---+
| m | n | o | p |
+---+---+---+---+
So all these arrangements are symmetric solutions:
(By shifting the rows:)
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| e | f | g | h | | i | j | k | l | | m | n | o | p |
+---------------+ +---------------+ +---------------+
| i | j | k | l | | m | n | o | p | | a | b | c | d |
+---------------+ +---------------+ +---------------+
| m | n | o | p | | a | b | c | d | | e | f | g | h |
+---------------+ +---------------+ +---------------+
| a | b | c | d | | e | f | g | h | | i | j | k | l |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
(By shifting the columns:)
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| b | c | d | a | | c | d | a | b | | d | a | b | c |
+---------------+ +---------------+ +---------------+
| f | g | h | e | | g | h | e | f | | h | e | f | g |
+---------------+ +---------------+ +---------------+
| j | k | l | i | | k | l | i | j | | l | i | j | k |
+---------------+ +---------------+ +---------------+
| n | o | p | m | | o | p | m | n | | p | m | n | o |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
(By shifting rows and columns:)
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| f | g | h | e | | k | l | i | j | | p | m | n | o |
+---------------+ +---------------+ +---------------+
| j | k | l | i | | o | p | m | n | | d | a | b | c |
+---------------+ +---------------+ +---------------+
| n | o | p | m | | c | d | a | b | | h | e | f | g |
+---------------+ +---------------+ +---------------+
| b | c | d | a | | g | h | e | f | | l | i | j | k |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
This list is not exhaustive, the number of shifts on the rows or columns is
arbitrary.
I know that this mailing list is not for general questions on constraint
programming, and concerns specifically Gecode. And my problem is that I do not
see how to implement symmetry breaking with Gecode.
I thought using LDSB (Lightweight Dynamic Symmetry Breaking), but after reading
the documentation and examples, I'm not sure that this tool makes it possible
to handle this case. From what I understand, LDSB manages permutations,
defining variables (or values) that are interchangeable.
But in my case it is not "isolated" permutations (only one permutation does not
give rise to a symmetry). So I do not how to use LDSB to manage shifts.
Similarly, I have not found a way to define constraints so as to break the
symmetries. Of course, it is always possible to find all the solutions
(symmetries included) and then detect and remove them, but the search space is
much larger.
Hence my questions: is it possible to use LDSB to implement symmetry breaking
"toroidal"? If not, is it possible to implement symmetry breaking "toroidal" in
another way?
I can provide more information if necessary. Anyway, thanks for help.
Martin Ludwag
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
