[SCIP] Question on symmetry handling with additional plugins

[Christopher Hojny]

Hi Matheus,

You are right, you should set p = |V| and q = k. The matrix M, however, 
is given by your x-variables, i.e., entry (v,i) is the SCIP variable 
x_{v, i}, and not 1.

Within the function SCIPcreateConsBasicOrbitope(), you thus should set

vars: your x-matrix with entries x_{v, i}
orbtitopeype: SCIP_ORBITOPETYPE_PARTITIONING
nspcons: |V|
nblocks: k
usedynamicprop: can be either TRUE or FALSE, you needed to check which 
works better for your application
resolveprop: TRUE or FALSE (reasoning as before)
ismodelcons: FALSE if you "only" want to handle symmetries or TRUE if 
you are really interested in a solution with sorted columns; I guess 
FALSE is what you are looking for
mayinteract: FALSE

Best regards,
Christopher


On 25-02-2024 19:45, Matheus Ota wrote:
> 	
> You don't often get email from matheusota at gmail.com. Learn why this is 
> important <https://aka.ms/LearnAboutSenderIdentification>
> 	
> 
> Hi Christopher and Marc,
> 
> Thanks for the reply! Could you please give more details on how to 
> construct the matrix for the orbitope plugin? I have essentially the 
> same setting as in the paper "Mixed-integer programming techniques for 
> the connected max-k-cut problem" by Hojny, Joormann, Lüthen & Schmidt. 
> In other words, I have a graph G = (V, E) and I want to partition the 
> vertices into k sets V_1, ..., V_k. My formulation has binary variables 
> x_{v, i} that indicate if vertex v belongs to V_i or not. I'm a bit 
> confused on how to construct the (p x q)-matrix M in this case. Should I 
> set p = |V|, q = k, and set M to be the all-ones matrix?
> 
> Thanks for your time!
> Matheus
> 
> On Fri, Feb 23, 2024 at 3:01 PM Marc Pfetsch 
> <pfetsch at mathematik.tu-darmstadt.de 
> <mailto:pfetsch at mathematik.tu-darmstadt.de>> wrote:
> 
> 
> 
>     Hi Matheus,
> 
>     the crucial point is whether and how symmetries are detected. This
>     depends on the SCIP version:
> 
>     - Beginning with the upcoming SCIP 9 your constraint handler needs to
>     implement callbacks that give information about the symmetries of your
>     constraints to SCIP. Then symmetries can be handled automatically.
> 
>     - In the "older" SCIP versiosn, your new constraint handler will
>     disable
>     symmetry detection, because SCIP does not have any symmetry information
>     about your constraint. Thus you would need to add orbitope constraints.
>     I do not think that there is an example, but you need a matrix of
>     binary
>     variables on which a full symmetry group acts by permuting the columns.
> 
>     Best
> 
>     Marc
> 
> 
> 
> 
>     On 23/02/2024 15:43, Matheus Ota wrote:
>      > Dear SCIP team,
>      >
>      > I've implemented in SCIP/C++ a branch-and-cut algorithm where the
>      > cutting-planes are separated via a constraint handler. I want to add
>      > symmetry handling methods on top of this algorithm (like shifted
>     column
>      > inequalities). So this leads me to the following question.
>      >
>      >   - Looking at the documentation I can see that I may be able to
>     do this
>      > easily by just activating a flag
>      > (https://www.scipopt.org/doc/html/SYMMETRY.php
>     <https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.scipopt.org%2Fdoc%2Fhtml%2FSYMMETRY.php&data=05%7C02%7C%7Cae86bc6d067e47c42fca08dc3632aa40%7Ccc7df24760ce4a0f9d75704cf60efc64%7C0%7C0%7C638444838445198056%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=xK64I0vxxYYp6gc%2FjcAcQY6OEjCata%2FD4k1dQfsrISQ%3D&reserved=0>
>      > <https://www.scipopt.org/doc/html/SYMMETRY.php
>     <https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.scipopt.org%2Fdoc%2Fhtml%2FSYMMETRY.php&data=05%7C02%7C%7Cae86bc6d067e47c42fca08dc3632aa40%7Ccc7df24760ce4a0f9d75704cf60efc64%7C0%7C0%7C638444838445207614%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=eXG0kcuC2RJ9yvM9YEenHu4L1NQAGU1a9URk39ZpJn0%3D&reserved=0>>). However I wonder if
>      > the additional cutting planes that I add iteratively will affect the
>      > symmetry handling. Do I need to manually include the orbitope
>     plugin?
>      > And if so, how do I do that? Is there any example?
>      >
>      > Thank you for your time,
>      > Matheus
>      >
>      > _______________________________________________
>      > Scip mailing list
>      > Scip at zib.de <mailto:Scip at zib.de>
>      > https://listserv.zib.de/mailman/listinfo/scip
>     <https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Flistserv.zib.de%2Fmailman%2Flistinfo%2Fscip&data=05%7C02%7C%7Cae86bc6d067e47c42fca08dc3632aa40%7Ccc7df24760ce4a0f9d75704cf60efc64%7C0%7C0%7C638444838445215422%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=uY60Z1b7BMi5LjRUJXv41aVOe0l9UpfpkNie%2FAwoNco%3D&reserved=0>
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto:Scip at zib.de>
>     https://listserv.zib.de/mailman/listinfo/scip
>     <https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Flistserv.zib.de%2Fmailman%2Flistinfo%2Fscip&data=05%7C02%7C%7Cae86bc6d067e47c42fca08dc3632aa40%7Ccc7df24760ce4a0f9d75704cf60efc64%7C0%7C0%7C638444838445221762%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=hMS%2FF4xGOt12RRXdYVU7j9ja6Pvxz2JhpRXiqqIIguI%3D&reserved=0>
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip