[SCIP] Symmetric-group symmetry breaking

[Christopher Hojny]

Dear Alex,

you have already mentioned the main ingredients to handle the action of
a symmetry group by symresacks / orbisacks: A symresack w.r.t. a
permutation g enforces a binary vector x to be lexicographically not
smaller than its permutation g(x). Thus, if we add a symresack
constraint for every permutation of the group, only those solutions will
survive that are lexicographically maximal in their orbits w.r.t. the
group action. As a consequence, all the symmetry is removed from the
problem.

However, as you already mentioned, this is impractical if the size of
the group is large (for S_N this means we would have to add N!
constraints). For this reason, we only add symresack constraints for a
set of generators of the symmetry group in SCIP. In general, this might
not break all the symmetry, because symresack constraints are considered
isolated. That is, we do not consider combinations of permutations from
different symresack constraints. For the symmetric group S_N and its
natural action on a set of N variables, however, this already breaks all
the symmetry, see slide 15. For your problem this means that it is
sufficient to add a symresack constraint for the N-1 next neighbor
transpositions (i, i+1) to handle all the symmetry in your problem, if I
got it right.

Regarding your question concerning the difference between symresacks and
orbisacks: From a theoretical point of view, there is no difference. An
orbisack is a special symresack, where the underlying permutation is a
composition of disjoint 2-cycles (for example, a transposition as in
your case). The reason why both types of constraints perform differently
may be based on the implementation of both constraint handlers. For
example, we can upgrade symresacks and orbisacks to so-called packing or
partitioning symreacks / orbisacks if we detect the presence of certain
set packing or partitioning constraints. In this case, the symresack
constraint handler adds a bunch of inequalities to the problem, while
the orbisack separates these constraints. However, this is only a guess.
If you send me your model and your setting files, I can have a look at
it to find an explanation for the different behavior.

To handle the symmetries of S_N best, I would suggest to add the
symresacks / orbisacks for all (N-1) next neighbor transpositions.
However, I do not really understand what you mean by

> 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.

If your permutation group contains all permutations of the size-N set,
how can the group act transitively on the larger set? Or is it
transitive on the size-N set and whenever we permute variables from the
size-N set, we also have to permute a set of further variables that are
associated with the variables from the size-N set? In the latter case,
only adding the symresacks for the next neighbor transpositions might
not be sufficient. Depending on the group structure, it may be
beneficial to use different approaches for that more knowledge on the
actual problem is necessary. For example, if it is a wreath product,
then linearly many inequalities suffice to handle all the symmetry (and
optimization over the corresponding polytope is solvable in polytime and
not NP-hard - the slides are a bit misleading in this case).

Best,
Christopher


On 06.02.19 04:33, Alex Meiburg wrote:
> 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
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
Dr. Christopher Hojny
Technische Universität Darmstadt
Fachbereich Mathematik, AG Optimierung
Dolivostraße 15
D-64293 Darmstadt

Phone: (+49) 6151 16 - 23496