Linear Programming with CPLEX

[cdvolko]

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 = IloNumExpr (env);
mod.add (sum_x >= 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 )
sum_x += 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 )
sum_x += 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 >= 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 >= 1 while minimizing sum_x_all. Why does CPLEX apparently set some x to 0? It does not make sense to me. How can I make the code run?

Thank you.

Claus