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

[Christian Schulte]

Hi Martin,

 

Maybe the following paper can help:

                Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, Toby Walsh:

Breaking Row and Column Symmetries in Matrix Models. CP 2002: 462-476

 

The idea is to use a lexical ordering constraint between rows and columns of a matrix to break some symmetries. See also the paragraph “Lexicographic constraints between variable arrays.” in Section 4.4.3 in MPG.

 

Cheers

Christian

 

--

Christian Schulte, www.gecode.org/~schulte

Professor of Computer Science, KTH, cschulte at kth.se

Expert Researcher, SICS, cschulte at sics.se

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Martin Ludwag
Sent: Friday, February 20, 2015 6:29 PM
To: users at gecode.org
Subject: [gecode-users] Toroidal symmetry breaking (with LDSB or not)

 

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/20150223/bf9270de/attachment.html>