Hi,
I'm new to CPLEX. I want to use it to solve a graph coloring problem exactly. Here's my code:
void calculateChromaticNumberExact ()
{
int i, j, numSubgraphs = graph>getNumSubgraphs (), numNodes = graph>getNumNodes ();
IloEnv env;
IloModel mod (env);
IloIntVar x numSubgraphs;
for (i = 0; i < numSubgraphs; i++)
{
mod.add (x [i] >= 0);
mod.add (x [i] <= numSubgraphs  1);
mod.add (IloMinimize (env, x [i]));
for (j = 0; j < i; j++)
if (graph>getEdge (i * numNodes + j))
mod.add (x [i] != x[j]);
}
IloCplex cplex (mod);
cplex.solve ();
chromaticNumberExact = cplex.getObjValue ();
}
This compiles, but it throws IloWrongUsage and terminates. What am I doing wrong?
x [i] is supposed to be the color of node i. If there is an edge between nodes i and j, x [i] must be != x [j]. The minimum number of colors is sought for.
Topic

Re: Graph coloring
20120806T15:26:43ZThis is the accepted answer. This is the accepted answer.Hi
You are using the Cplex solver that does not support the constraints x [i] != x[j]
If you want to express it in linear math programming, you you used a big M formulation. I suggest you post your question to the dedicated forum on which you will be able to have the best formulation in function of your actual problem : the forum Mathematical Programming  General of the IBM ILOG Optimization Forums.
Eventually you can use constraint programming that support the != constraint by using the CP Solver. That is replacing:
IloCplex cplex (mod); cplex.solve (); chromaticNumberExact = cplex.getObjValue ();
by
IloCP cp (mod); cp.solve (); chromaticNumberExact = cp.getObjValue ();
Hope that helps