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 ();
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);
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.
GGR 270002SS1037 Posts
Re: Graph coloring2012-08-06T15: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 ();
IloCP cp (mod); cp.solve (); chromaticNumberExact = cp.getObjValue ();
Hope that helps