Adding symmetry-breaking constraints

On some models symmetry poses a real problem for solvers. Here is an example of a sports related scheduling problem. We achieve a speedup of 35x by adding constraints that break a number of symmetries in the model. The results here are with Gurobi.

Modern solvers have also built-in facilities to detect and do something about symmetry. E.g. Gurobi has the option Symmetry which can be set to 2 (aggressive). I never had much luck with this. Indeed the results are:

Cplex shows very similar behavior:

Note that Cplex provides a large number of settings for the symmetry option:

That is probably just an educational tool to teach the user a lesson about combinatorial explosion: finding the right settings for your model.

Often solver suppliers say this is a solved problem:

This is an example that shows the fixes are at least insufficient. The algorithms do not handle this problem always in a satisfactory way.