[SCIP] Looking for example how to express symmetry groups

[Christopher Hojny]

Dear Johann-Tobias,

The dense symmetry format is just an array that contains for every 
variable index its image w.r.t. a permutation symmetry. For example, the 
array

[0,3,1,2]

encodes the permutation that maps

0 -> 0
1 -> 3
2 -> 1
3 -> 2

which is equivalent to the cycle notation (1,3,2).

The most generic type of symmetry handling constraint is the symresack 
constraint. For a given variable vector x (encoded as array) and a 
permutation perm, it enforces that x is not lexicographically smaller 
than perm(x). In case perm is an involution, we have a specialized 
implementation via the orbisack constraint handler. If you do not want 
to make the distinction whether you are dealing with an involution on 
your own, you can make use of the function

cons_symresack.h:SCIPcreateSymbreakCons()

which will decide whether a symresack or orbisack constraint is created.

If you are looking for an example of how to make use of this function, 
you can have a look at, e.g.,

https://github.com/christopherhojny/relaxation_complexity/blob/master/scip-code/src/probdata_rc_compact.c#L835

If you know that your symmetry group has an additional structure, we 
also support orbitopes. These are constraints enforcing the following. 
Suppose you can assign your variables to a matrix such that a symmetry 
(sub)group acts on the variables by permuting the columns. Then, the 
orbitope enforces that the columns are sorted lexicographically 
non-increasingly. A code example can be found, for instance, here

https://github.com/christopherhojny/globally-solving-MSSC/blob/main/src/probdata_clustering.c#L596

Orbitopes and symresacks/orbisacks can be combined, provided you use a 
compatible variable order in all types of constraints. These tools are, 
however, not able to handle symmetries on non-binary variables at the 
moment.

Please let me know if you need more details.

Regarding your comment about SCIP not finding all symmetries, I have two 
further points that I would like to mention. First, SCIP is also able to 
detect reflection symmetries. This feature can be enabled by setting the 
parameter

propagating/symmetry/symtype = 1

Maybe this detects the remaining symmetries of your problem. Second, 
SCIP can only automatically detect permutation and reflection symmetries 
(the latter encoded as signed permutations). If you know that other 
groups such as general linear groups over a finite field define 
symmetries of your problem, SCIP will not be able to recognize them.

Best regards,
Christopher


On 12-06-2025 18:18, Johann-Tobias Schäg wrote:
> [You don't often get email from johann-tobias at xn--schg-noa.de. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]
> 
>> Marc Pfetsch <pfetsch at mathematik.tu-darmstadt.de> hat am 12.06.2025 14:08 CEST geschrieben:
>>
>>
>> Dear Johann-Tobias,
>>
>> the main workhorse for symmetry handling is prop_symmetry. This
>> propagator stores the symmetry information that you are probably
>> interested in. It stores the generators of the permutation group in
>> dense format.
> 
> Is that dense format documented somewhere?
> 
>>
>> An explanation of the symmetry handling capabilities is available in the
>> SCIP Release Reports (see the SCIP webpage).
>>
>> Note that SCIP can also handle symmetries on non-binary variables.
> 
> Neat, the docs i linked only mentioned binary variables only so i inferred that.
> 
>>
>> I hope that these pointers give you enough information. Otherwise, we
>> would need more specific questions.
> 
> Is there an example where the user provides a description of some/all symmetries of a problem? (possibly in the C API).
> 
> Sincerely,
> Johann-Tobias
> 
>>
>> Best
>>
>> Marc
>>
>>
>> On 12/06/2025 11:58, Johann-Tobias Schäg wrote:
>>> I am aware that there are mutliple ways to handle symmetries in SCIP
>>> https://www.scipopt.org/doc/html/cons__orbisack_8h.php
>>> <https://www.scipopt.org/doc/html/cons__orbisack_8h.php>
>>> https://www.scipopt.org/doc/html/cons__orbitope_8h.php
>>> <https://www.scipopt.org/doc/html/cons__orbitope_8h.php>
>>> https://www.scipopt.org/doc/html/cons__symresack_8h.php
>>> <https://www.scipopt.org/doc/html/cons__symresack_8h.php>
>>> All those are for binary variables.
>>> I occasionally encounter 0-1 ILP which have symmetries so large that
>>> SCIP fails to (fully) detect them. I asked on the OR stack exchange
>>> whether there is a standardized format for symmetry groups:
>>> https://or.stackexchange.com/questions/13187/are-there-existing-formats-to-express-symmetries-between-variables-in-milp?noredirect=1#comment28418_13187 <https://or.stackexchange.com/questions/13187/are-there-existing-formats-to-express-symmetries-between-variables-in-milp?noredirect=1#comment28418_13187> and was pointed towards SCIP being potentially interesting for that.
>>> Is there some examples which use those constraints handlers?
>>> The documentation i linked above is to dense for me to make sense of.
>>> Sincerely,
>>> Johann-Tobias Schäg
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> https://listserv.zib.de/mailman/listinfo/scip
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip