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, [email protected]
Expert Researcher, SICS, [email protected]
From: [email protected] [mailto:[email protected]] On Behalf Of
Martin Ludwag
Sent: Friday, February 20, 2015 6:29 PM
To: [email protected]
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
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
