Originally posted by: cdvolko

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.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: GGR

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
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: cdvolko

Thanks for your reply. I'll try both things.
#ConstraintProgramming-General
#DecisionOptimization