Graph coloring with ILCP / Cplex

[cdvolko]

Hi,

I am trying to use ILCP or Cplex to solve the graph coloring problem exactly. The following code is an attempt to implement the recommended way of solving this problem as an integer program. Unfortunately this code does not compile due to bad usage of IloSum. Moreover, I do not know how to specify the objective function for this (which should be: minimize the maximum colornumber used).

Meaning of the variables:
x [j] == 1 iff node i has color j.

void calculateChromaticNumberExact ()
{
int i, j, k, numSubgraphs = graph->getNumSubgraphs (), numNodes = graph->getNumNodes ();
IloEnv env;
IloModel mod (env);
IloIntVar x [numSubgraphs] [numSubgraphs];

for (i = 0; i < numSubgraphs; i++)
{
mod.add (IloSum (x ) == 1);
for (j = 0; i < numSubgraphs; i++)
{
mod.add (x [j] >= 0);
mod.add (x [j] <= 1);
}
for (k = 0; k < i; k++)
if (graph->getEdge (i * numNodes + k))
for (j = 0; j < numSubgraphs; j++)
mod.add (x [j] + x [k] [j] <= 1);
}

IloCP cp (mod);
cp.solve ();

chromaticNumberExact = cp.getObjValue ();
}