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

Pinned topic Graph coloring

‏2012-08-06T13:58:46Z |

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
    34 Posts

    Re: Graph coloring


    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
  • cdvolko
    2 Posts

    Re: Graph coloring

    Thanks for your reply. I'll try both things.