Break symmetry for k-clustering

[phspo]

Any permutation of cluster assignment is an "equivalent" valid solution, therefore forcing one "fixed" cluster labeling could decrease the solution space. (For instance force node 1 to always be in cluster 1)

[schrins]

The problem for such optimizations are, that we do not know anything about the internals of CPLEX. I had a similar issue with direct haplotype phasing via CPLEX and the whole thing ended up way slower after I added symmetrie breaking inequalities. The reason for this was that CPLEX was doing a lot of branching while searching for better solutions, but the majority of the branches ran into the problem of violating the symmetry breaking inequalities. However, in order to violate these inequalities, a lot of fixed variables were needed (i.e. a deep branching depth), because the inqualities could be easily fooled with fractional solutions.

For example: With 6 clusters, you have 720 equivalent optimal solutions. The symmetry breaking inequalities make 719 of them infeasable, allowing only one of them. CPLEX might now come close to any of those 719 solutions, but has to drop the progress, because the inequalities become violated once too close the optimal solutions. You would then have to wait until CPLEX finds the 720th solution by chance.