[SCIP] Question on symmetry handling with additional plugins

[Matheus Ota]

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> 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://www.scipopt.org/doc/html/SYMMETRY.php>). 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
> > https://listserv.zib.de/mailman/listinfo/scip
> _______________________________________________
> 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/20240225/3fd64248/attachment.html>