3
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$
  1. Search for symmetry breaking constraints. Here's a small but common example: https://math.stackexchange.com/questions/4415333/assymetric-graph-coloring-formulation

  2. Fix some variables. E.g. Greedily find the largest clique in your graph, and hard code the colors of the vertices in this clique.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.