search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
406 stars 67 forks source link

What are the uses of nauty in SCIP? #87

Closed j2kun closed 9 months ago

j2kun commented 9 months ago

I'm doing background research on graph isomorphism and I wanted to find projects who use it and understand the use cases. I noticed nauty is vendered in SCIP and I am curious what the use case is in SCIP. I understand linear solvers well enough, but I wasn't aware of any graph isomorphism solver heuristics or anything like that.

Could a familiar maintainer please reply with some information about this?

j2kun commented 9 months ago

Ah, is this "orbital branching"?

svigerske commented 9 months ago

Yes, that's one thing. It's for finding and exploiting symmetries in the problem formulation.

pfetsch commented 9 months ago

SCIP uses graph isomorphism tools to compute the symmetry group of mixed integer (nonlinear) programs. It currently supports bliss and nauty. In addition, the graph isomorphism preprocessor sassy is used. The default is to use sassy and bliss. What do you mean by graph isomorphism solver heuristics? Is sassy such a heuristic?

An overview of the techniques used in SCIP is given in the SCIP Optimization Suite release reports, see the SCIP webpage.

j2kun commented 9 months ago

Those reports have more than enough information. Thanks! (I meant using GI in formulating primal heuristics)