[SCIP] Looking for example how to express symmetry groups

Fri Jun 13 09:43:06 CEST 2025

Dear Johann-Tobias,

There is no uniform answer to your question, this highly depends on the 
types of symmetries that you want to handle. The three constraint 
handlers are only able to handle single permutations or special actions 
of symmetric groups. If you have other symmetries, e.g., reflections or 
rotations, then these constraint handlers cannot deal with them.

Best regards,
Christopher

On 12-06-2025 19:14, 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 ]
> 
>> Christopher Hojny <c.hojny at tue.nl> hat am 12.06.2025 18:50 CEST geschrieben:
>>
>>
>> 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.
> 
> I have not comprehended all the above. You say there are some symmetries SCIP can not detect. But can they be expressed to SCIP through the methods outlined in above github links?
> 
>>
>> 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
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip