I have a very straightforward ILP model of vertex coloring that I'm trying to solve with CPLEX.
With a binary variable $x_{vc}$ for every $(v,c) \in \{ V \times C\}$ there is a constraint $$ \sum_{c \in C} x_{vc} = 1 \quad \forall v \in V$$ and a constraint $$ x_{vc} + x_{uc} \leq 1, \quad \forall c \in C, \forall (u,v) \in E.$$ Without providing the remainder of the model suffice to say that the model minimizes the number of colors in use.
The good news is that on my 8-core machine this model will permit the "school1.col" instance (from the DIMACS data set) to be solved in ~150s. This instance has $|V|=385, |E| \approx 18,000, \chi=14$. That was the good news.
Now, if I try to solve a multi-coloring problem, asking for each vertex to be assigned two colors, it seems to me that it is sufficient to change the first constraint to, $$ \sum_{c \in C} x_{vc} = 2 \quad \forall v \in V.$$
After ~4 hours of elapsed time CPLEX has still not found a feasible solution. This seems like a huge performance gap to me. So my question is whether people think CPLEX might have some analysis built into it specifically targeting models of the generic coloring-type. Or is there a better explanation?
Many thanks.