Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3.
The solution to the colouring problem can be 1,0,1,1 or 0,1,0,0, both are essentially the same. How I can model redundant constraints for this?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Search for symmetry breaking constraints. Here's a small but common example: https://math.stackexchange.com/questions/4415333/assymetric-graph-coloring-formulation
Fix some variables. E.g. Greedily find the largest clique in your graph, and hard code the colors of the vertices in this clique.
