Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Linear Programming with CPLEX (http://www.velocityreviews.com/forums/t953697-linear-programming-with-cplex.html)

cdvolko@gmail.com 10-21-2012 04:28 PM

Linear Programming with CPLEX
 
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


All times are GMT. The time now is 01:42 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.