Graph coloring with ILCP / Cplex

C

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 ();
}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top