[gecode-users] Toroidal symmetry breaking (with LDSB or not)

[Martin Ludwag]

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
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20150220/3d11fb4b/attachment.html>