Dealing with Symmetry. Commercial solver defaults vs manual implementations

Question

Since the modeler has domain/business knowledge of the problem being solved, is it possible to manually implement Isomorphism Pruning or Orbital branching and beat the default methods implemented by the solvers under the hood. Also, some of the advice, especially here on OR-SE is to not even add symmetry breaking constraints and let the solver exploit/handle it. Thoughts?

Manually implementing isomorphism pruning or orbital branching is quite involved. Anyone can provide code sample using a commercial solver (Gurobi/Cplex/Xpress)?

Answer 1

There might be automatic settings and tunings inside the solver that are not perfect and might choose not to use orbital branching for an instance although it might be beneficial. In that case the first thing to try would be to change a symmetry setting in a solver to something like "aggressive" (or at least non-default).

Implementing orbital branching for those solvers that provide branching callbacks is not all that hard as long as you have a way to identify the orbits which can be done using open-source graph isomorphism packages (like nauty and saucy). It's not likely to be more efficient than what the solvers are using inside, but it is at least possible. Still I would not expect a huge gain except for solvers that don't have symmetry handling at all (like some open source solvers).

Note that its not enough to know the orbits upfront, one also needs to know how the orbits change when branching, so the domain/business knowledge might not be all that helpful.

Answer 2

As far as symmetry breaking constraints v. leaving the solver to deal with the symmetry, I think that is an empirical question, meaning you can try both (with reasonably short time limits) and see which is better. The solver may have parameter settings for how (or how aggressively) it deals with symmetry, so you might be trying more than two scenarios before deciding which looks most promising.

For what it is worth, I have in the past had decent luck with symmetry breaking constraints using CPLEX, although in fairness I usually don't bother to test them versus the most aggressive parameter settings.