<div dir="ltr">> If your permutation group contains all permutations of the size-N set,<br><div>> how can the group act transitively on the larger set? Or is it</div><div>> transitive on the size-N set and whenever we permute variables from the<br></div><div>> size-N set, we also have to permute a set of further variables that are<br></div><div>> associated with the variables from the size-N set? I <br></div><div><br></div><div>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.<br></div><div><br></div><div>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!<br></div><div><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">-- Alexander Meiburg<br></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Feb 6, 2019 at 5:14 AM Christopher Hojny <<a href="mailto:hojny@mathematik.tu-darmstadt.de">hojny@mathematik.tu-darmstadt.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear Alex,<br>
<br>
you have already mentioned the main ingredients to handle the action of<br>
a symmetry group by symresacks / orbisacks: A symresack w.r.t. a<br>
permutation g enforces a binary vector x to be lexicographically not<br>
smaller than its permutation g(x). Thus, if we add a symresack<br>
constraint for every permutation of the group, only those solutions will<br>
survive that are lexicographically maximal in their orbits w.r.t. the<br>
group action. As a consequence, all the symmetry is removed from the<br>
problem.<br>
<br>
However, as you already mentioned, this is impractical if the size of<br>
the group is large (for S_N this means we would have to add N!<br>
constraints). For this reason, we only add symresack constraints for a<br>
set of generators of the symmetry group in SCIP. In general, this might<br>
not break all the symmetry, because symresack constraints are considered<br>
isolated. That is, we do not consider combinations of permutations from<br>
different symresack constraints. For the symmetric group S_N and its<br>
natural action on a set of N variables, however, this already breaks all<br>
the symmetry, see slide 15. For your problem this means that it is<br>
sufficient to add a symresack constraint for the N-1 next neighbor<br>
transpositions (i, i+1) to handle all the symmetry in your problem, if I<br>
got it right.<br>
<br>
Regarding your question concerning the difference between symresacks and<br>
orbisacks: From a theoretical point of view, there is no difference. An<br>
orbisack is a special symresack, where the underlying permutation is a<br>
composition of disjoint 2-cycles (for example, a transposition as in<br>
your case). The reason why both types of constraints perform differently<br>
may be based on the implementation of both constraint handlers. For<br>
example, we can upgrade symresacks and orbisacks to so-called packing or<br>
partitioning symreacks / orbisacks if we detect the presence of certain<br>
set packing or partitioning constraints. In this case, the symresack<br>
constraint handler adds a bunch of inequalities to the problem, while<br>
the orbisack separates these constraints. However, this is only a guess.<br>
If you send me your model and your setting files, I can have a look at<br>
it to find an explanation for the different behavior.<br>
<br>
To handle the symmetries of S_N best, I would suggest to add the<br>
symresacks / orbisacks for all (N-1) next neighbor transpositions.<br>
However, I do not really understand what you mean by<br>
<br>
> If it matters, when I say I have a full symmetric group on N<br>
> variables, it actually acts on more -- a single "transposition"<br>
> permutes a variety of variables in the whole problem. Really, I<br>
> should say that I have a transitive action of S_N onto a larger set<br>
> of variables, and N~10.<br>
<br>
If your permutation group contains all permutations of the size-N set,<br>
how can the group act transitively on the larger set? Or is it<br>
transitive on the size-N set and whenever we permute variables from the<br>
size-N set, we also have to permute a set of further variables that are<br>
associated with the variables from the size-N set? In the latter case,<br>
only adding the symresacks for the next neighbor transpositions might<br>
not be sufficient. Depending on the group structure, it may be<br>
beneficial to use different approaches for that more knowledge on the<br>
actual problem is necessary. For example, if it is a wreath product,<br>
then linearly many inequalities suffice to handle all the symmetry (and<br>
optimization over the corresponding polytope is solvable in polytime and<br>
not NP-hard - the slides are a bit misleading in this case).<br>
<br>
Best,<br>
Christopher<br>
<br>
<br>
On 06.02.19 04:33, Alex Meiburg wrote:<br>
> Hi all,<br>
> <br>
> I'm trying to understand how to most effectively use the orbisack /<br>
> symresack constraints. I have a set of N variables (where N ~ 10) that have<br>
> the fully symmetric group of symmetry: any permutation of them is valid. I<br>
> initially implemented this by creating N-1 symresack constraints: one for<br>
> swapping variables 1 and 2, one for swapping 2 and 3 ... one for N-1 and N.<br>
> (By the way, I noticed, oddly, that allowing it to 'upgrade' these two<br>
> orbisacks led to a ~5x slowdown over forcing them to stay symresacks. Any<br>
> idea why that would be the case?). Then for comparison, I tried a creating<br>
> only two constraints: one for a transposition of the first two variables,<br>
> and one for the N-cycle -- because these two generate the two whole<br>
> symmetric group.<br>
> <br>
> Then I realized that I don't think this is actually how it works. My<br>
> understanding of the way they enforce symmetry breaking, based on the SCIP<br>
> 5.0 release notes and<br>
> <a href="http://www.iasi.cnr.it/aussois/web/uploads/2018/slides/hojnyc.pdf" rel="noreferrer" target="_blank">http://www.iasi.cnr.it/aussois/web/uploads/2018/slides/hojnyc.pdf</a> , is that<br>
> the constraint only enforces for a *single* permutation gamma; adding<br>
> multiple in won't imply all the potential products of those permutations.<br>
> <br>
> That PDF mentions that full facet inequalities are known for Sn and<br>
> Sn[wreath]Sm, which are the two I'm most interested in, but also that<br>
> optimizing over them is hard. Well, integer programming is hard, so I'm not<br>
> sure how meaningful that is.<br>
> <br>
> Anyway, I'm looking for advice on how to best do this. I don't care about<br>
> any objective function, or counting solutions, I just want to determine<br>
> feasibility or not, and the symmetry breaking is just supposed to reduce<br>
> redundant search time. Adding in one or two symresacks should (to my<br>
> understanding) roughly cut the search space in half, but adding in all N!<br>
> would be impractical. Do you think then that, for instance, adding in all<br>
> pairwise transpositions is a good balance? Or what?<br>
> <br>
> If it matters, when I say I have a full symmetric group on N variables, it<br>
> actually acts on more -- a single "transposition" permutes a variety of<br>
> variables in the whole problem. Really, I should say that I have a<br>
> transitive action of S_N onto a larger set of variables, and N~10.<br>
> <br>
> I appreciate any advice or insight. Thank you!<br>
> <br>
> Sincerely,<br>
> Alexander Meiburg<br>
> <br>
> <br>
> _______________________________________________<br>
> Scip mailing list<br>
> <a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
> <a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
> <br>
<br>
-- <br>
Dr. Christopher Hojny<br>
Technische Universität Darmstadt<br>
Fachbereich Mathematik, AG Optimierung<br>
Dolivostraße 15<br>
D-64293 Darmstadt<br>
<br>
Phone: (+49) 6151 16 - 23496<br>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>