Dear all,
I want to implement the column generation approach for graph coloring usingILOG CPLEX (as described in the original paper by Mehrotra and Trick 1995).. My code looks as follows:
int numSubgraphs = graph>getNumSubgraphs ();
bool *maximalIndependentSet = new bool [numSubgraphs];
IloEnv env;
IloModel mod (env);
IloNumExpr x [numSubgraphs];
IloNumExprArray sum_x (env, numSubgraphs);
IloNumExpr sum_x_all (env);
int i, j, current;
for (i = 0; i < numSubgraphs; i++)
{
sum_x [i] = IloNumExpr (env);
mod.add (sum_x [i] >= 1);
}
sum_x_all = IloNumExpr (env);
mod.add (IloMinimize (env, sum_x_all));
IloCplex cp (mod);
generateFirstMaximalIndependentSet (maximalIndependentSet);
x [0] = IloNumExpr (env);
mod.add (x [0] >= 0);
mod.add (x [0] <= 1);
sum_x_all += x [0];
for (i = 0; i < numSubgraphs; i++)
if (!maximalIndependentSet [i])
sum_x [i] += x [0];
current = 1;
x [current] = IloNumExpr (env);
mod.add (x [current] >= 0);
mod.add (x [current] <= 1);
sum_x_all += x [current];
for (i = 0; i < numSubgraphs; i++)
if (maximalIndependentSet [i])
sum_x [i] += x [current];
// for testing purposes
cp.exportModel("model.lp");
cp.solve ();
This is only the part of the code that deals with the primal problem. This code leads to an error message of the following kind:
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative"
is accessing CPLEX 12 with option(s): "e m b q ".
Infeasibility row 'id11': 0 >= 1.
The only constraints with >= 1 are the sum_x [i] >= 1 constraints. I would like to know whether this error occurs. After all CPLEX is supposed to find solutions for x [0] and x [1] so that for all i, sum_x [i] >= 1 while minimizing sum_x_all. Why does CPLEX apparently set some x [i] to 0? It does not make sense to me. How can I make the code run?
Thank you.
Claus
