Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Linear Programming with CPLEX

Thread Tools

Linear Programming with CPLEX
Posts: n/a
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.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.

Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Graph coloring with ILCP / Cplex C++ 0 08-08-2012 03:06 PM
Looking for Source code for Linear programming leo C Programming 2 02-14-2006 05:28 PM
Looking for source code for Linear programming leo C++ 1 02-14-2006 07:15 AM
Code for linear congruences, diophantine linear equations Java 1 11-15-2005 12:23 PM
Re: Cplex hangs in Perl system command Paul A. Rubin Perl 2 08-05-2003 10:15 PM