Topic
• 2 replies
• Latest Post - ‏2012-08-07T12:45:58Z by cdvolko
cdvolko
2 Posts

# Pinned topic Graph coloring

‏2012-08-06T13:58:46Z |
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.
Updated on 2012-08-07T12:45:58Z at 2012-08-07T12:45:58Z by cdvolko
• GGR
44 Posts

#### Re: Graph coloring

‏2012-08-06T15:26:43Z
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
• cdvolko
2 Posts

#### Re: Graph coloring

‏2012-08-07T12:45:58Z
Thanks for your reply. I'll try both things.