Linear Programming with CPLEX

Discussion in 'C++' started by cdvolko@gmail.com, Oct 21, 2012.

  1. Guest

    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
    , Oct 21, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul A. Rubin

    Re: Cplex hangs in Perl system command

    Paul A. Rubin, Aug 4, 2003, in forum: Perl
    Replies:
    2
    Views:
    3,605
    Paul A. Rubin
    Aug 5, 2003
  2. Replies:
    1
    Views:
    1,097
    Roedy Green
    Nov 15, 2005
  3. leo
    Replies:
    2
    Views:
    750
    Julian V. Noble
    Feb 14, 2006
  4. Replies:
    0
    Views:
    357
  5. Replies:
    2
    Views:
    31
    Akira Li
    Jun 1, 2014
Loading...

Share This Page