[SCIP] Symmetric-group symmetry breaking

Thu Feb 7 04:49:20 CET 2019

> 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? I

It's the latter. In this instance, I have a matrix of NxN variables. I can
freely permute the "basis vectors" of my matrix -- simultaneously permuting
the rows and columns, which in turns permutes the matrix elements. So if I
swap one pair of rows (and thus also one pair of columns), in induces 2N-2
swaps on a sparse collection of the N^2 variables. So what I mean is that
the abstract symmetry *group* is S_n, but that it's acting on a larger set
of variables nontrivially.

I see why, if it was just N variables that were permuted, then the
transpositions would suffice to break all symmetry. I'll have to think on
if I accomplish something similar for my problem. Thank you!

-- Alexander Meiburg

On Wed, Feb 6, 2019 at 5:14 AM Christopher Hojny <
hojny at mathematik.tu-darmstadt.de> wrote:

> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190206/05ea647c/attachment.html>