[SCIP] Symmetric-group symmetry breaking

[Alex Meiburg]

Hi all,

I'm trying to understand how to most effectively use the orbisack /
symresack constraints. I have a set of N variables (where N ~ 10) that have
the fully symmetric group of symmetry: any permutation of them is valid. I
initially implemented this by creating N-1 symresack constraints: one for
swapping variables 1 and 2, one for swapping 2 and 3 ... one for N-1 and N.
(By the way, I noticed, oddly, that allowing it to 'upgrade' these two
orbisacks led to a ~5x slowdown over forcing them to stay symresacks. Any
idea why that would be the case?). Then for comparison, I tried a creating
only two constraints: one for a transposition of the first two variables,
and one for the N-cycle -- because these two generate the two whole
symmetric group.

Then I realized that I don't think this is actually how it works. My
understanding of the way they enforce symmetry breaking, based on the SCIP
5.0 release notes and
http://www.iasi.cnr.it/aussois/web/uploads/2018/slides/hojnyc.pdf , is that
the constraint only enforces for a *single* permutation gamma; adding
multiple in won't imply all the potential products of those permutations.

That PDF mentions that full facet inequalities are known for Sn and
Sn[wreath]Sm, which are the two I'm most interested in, but also that
optimizing over them is hard. Well, integer programming is hard, so I'm not
sure how meaningful that is.

Anyway, I'm looking for advice on how to best do this. I don't care about
any objective function, or counting solutions, I just want to determine
feasibility or not, and the symmetry breaking is just supposed to reduce
redundant search time. Adding in one or two symresacks should (to my
understanding) roughly cut the search space in half, but adding in all N!
would be impractical. Do you think then that, for instance, adding in all
pairwise transpositions is a good balance? Or what?

If it matters, when I say I have a full symmetric group on N variables, it
actually acts on more -- a single "transposition" permutes a variety of
variables in the whole problem. Really, I should say that I have a
transitive action of S_N onto a larger set of variables, and N~10.

I appreciate any advice or insight. Thank you!

Sincerely,
Alexander Meiburg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190205/41bc2809/attachment.html>