Topic
  • 12 replies
  • Latest Post - ‏2013-12-02T06:32:29Z by DanielJunglas
Industrial88
Industrial88
8 Posts

Pinned topic Getting unbounded direction in C++ API

‏2013-11-25T16:59:50Z |

Dear all,

I'm trying to get unbounded directions of my LP model through "getRay" function in  C++ API. Actually, one of my model decision variable, called "nou8", is type of "IloNumVar" . In other words, it's not kind of "IloNumVarArray".  On the other hand, "getRay" arguments must be type of arrays. How can I overcome this difficulty?

Thanks

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-25T17:06:37Z  

    You use the getRay() function like this:

    IloNumVarArray var(env);
    IloNumArray val(env);
    cplex.getRay(val, var);

    After this the unbounded ray will be in the var/val arrays. Note that the arrays only contain the non-zero values of the unbounded direction, see also the reference documentation.

  • Industrial88
    Industrial88
    8 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-25T17:33:16Z  

    You use the getRay() function like this:

    IloNumVarArray var(env);
    IloNumArray val(env);
    cplex.getRay(val, var);

    After this the unbounded ray will be in the var/val arrays. Note that the arrays only contain the non-zero values of the unbounded direction, see also the reference documentation.

    Thanks for your comment.

    As what mentioned above, the "getRay" function only returns non-zero elements of the unbounded direction. I got rays using "getRay" function, then store them into IloNum arrays, and finally use them to build a feasibility cut (in closed form (b - By)*(ray) < 0) in Benders decomposition. For instance, we might have the following term in our feasibility cut:

    for(i=0;i<I;i++)
            rhs += cost[i]*demand_price[Cut][i];

    Where rhs, cost, Cut, and demand_price are IloExpr, IloNumArray, algorithm iteration counter, and IloNumArray, respectively. Particularly, demand_price[Cut][i] denotes unbounded direction in iteration Cut which was given by "getRay" function like:

     for(i=0; i < I; i++)
            cplex_sub.getRay(demand_price[Cut][i], d[i]); d[i] implies dual decision variable.

    Is this way of definition is right? Actually, my code crashes and breaks due to an "Unhandled exception"  which is related to this part of my code! feasibility cut!

    for(i=0;i<I;i++)
            rhs += cost[i]*demand_price[Cut][i];

    Any comments or favor would be highly appreciated.

     

    Updated on 2013-11-26T00:18:16Z at 2013-11-26T00:18:16Z by Industrial88
  • hllsen
    hllsen
    2 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-26T06:53:35Z  

    Thanks for your comment.

    As what mentioned above, the "getRay" function only returns non-zero elements of the unbounded direction. I got rays using "getRay" function, then store them into IloNum arrays, and finally use them to build a feasibility cut (in closed form (b - By)*(ray) < 0) in Benders decomposition. For instance, we might have the following term in our feasibility cut:

    for(i=0;i<I;i++)
            rhs += cost[i]*demand_price[Cut][i];

    Where rhs, cost, Cut, and demand_price are IloExpr, IloNumArray, algorithm iteration counter, and IloNumArray, respectively. Particularly, demand_price[Cut][i] denotes unbounded direction in iteration Cut which was given by "getRay" function like:

     for(i=0; i < I; i++)
            cplex_sub.getRay(demand_price[Cut][i], d[i]); d[i] implies dual decision variable.

    Is this way of definition is right? Actually, my code crashes and breaks due to an "Unhandled exception"  which is related to this part of my code! feasibility cut!

    for(i=0;i<I;i++)
            rhs += cost[i]*demand_price[Cut][i];

    Any comments or favor would be highly appreciated.

     

    As far as I understand, instead of using d[i] as an input argument in getRay function, you should feed it with an empty (just initialized) IloNumVarArray. getRay will "fill" this IloNumVarArray with the variables that are non-zero in the extreme ray -- and the corresponding values of these variables will be in the IloNumArray you feed to the getRay function. That is, this usage (cplex_sub.getRay(demand_price[Cut][i], d[i]);) seems wrong, inspect Daniel's example.


    Then, of course, you need to identify the variables in the IloNumVarArray you ended up with -- afaik, they could be in any order (am I right?). You can use getID function to find which variable is which.

    Cheers,

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-26T07:05:16Z  
    • hllsen
    • ‏2013-11-26T06:53:35Z

    As far as I understand, instead of using d[i] as an input argument in getRay function, you should feed it with an empty (just initialized) IloNumVarArray. getRay will "fill" this IloNumVarArray with the variables that are non-zero in the extreme ray -- and the corresponding values of these variables will be in the IloNumArray you feed to the getRay function. That is, this usage (cplex_sub.getRay(demand_price[Cut][i], d[i]);) seems wrong, inspect Daniel's example.


    Then, of course, you need to identify the variables in the IloNumVarArray you ended up with -- afaik, they could be in any order (am I right?). You can use getID function to find which variable is which.

    Cheers,

    You are right, the order of the elements in the array returned by getRay() is unspecified. You are also right that getRay() takes no input arguments. The two arrays passed to it are output arguments. getRay() will just clear them and then put the output vector into them.

    An example of using the getRay() function in Benders decompostiion can be found in the ilobendersatsp.cpp example shipped with CPLEX. Maybe check this example to see if you are doing things the right way.

  • Industrial88
    Industrial88
    8 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-26T17:57:51Z  

    You are right, the order of the elements in the array returned by getRay() is unspecified. You are also right that getRay() takes no input arguments. The two arrays passed to it are output arguments. getRay() will just clear them and then put the output vector into them.

    An example of using the getRay() function in Benders decompostiion can be found in the ilobendersatsp.cpp example shipped with CPLEX. Maybe check this example to see if you are doing things the right way.

    Thank you hllsen and Daniel,

    I'm still have difficulty to use "getRay" function.  I don't know how to map each extreme direction to the corresponding expression in the feasibility cut. More specifically, I've know idea how to build my feasibility cut by the values in the val and var arrays! I was wondering if you would please do me a favor.!

     

    Updated on 2013-11-27T19:57:29Z at 2013-11-27T19:57:29Z by Industrial88
  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-29T15:28:23Z  

    Thank you hllsen and Daniel,

    I'm still have difficulty to use "getRay" function.  I don't know how to map each extreme direction to the corresponding expression in the feasibility cut. More specifically, I've know idea how to build my feasibility cut by the values in the val and var arrays! I was wondering if you would please do me a favor.!

     

    I am not clear about what you mean that there are 3 sets of extreme directions in your feasibility cut.

    Anyway, function getRay() will only return one single ray for a problem instance. Calling it multiple times will always return the same ray.

    I am not sure but maybe this can help you: Assuming that all your variables are stored in an IloNumVarArray y then the following code produces a dense ray vector, the elements of which are in 1:1 correspondance to y (note that the code is simple but not efficient):

    IloNumArray sparseVals(env);
    IloNumVarArray sparseVars(env);
    cplex.getRay(sparseVals, sparseVars);
    IloNumArray ray(env);
    for (IloInt j = 0; j < y.getSize(); ++j) {
       // Find the value for y[j] in the ray (if any)
       bool found = false;
       for (IloInt k = 0; k < sparseVars.getSize(); ++k) {
          if ( y[j].getId() == sparseVars[k].getId() ) {
             ray.add(sparseVals[k]);
             found = true;
             break;
          }
       }
       if ( !found ) {
          // Variable y[j] not found -> zero coefficient in ray
          ray.add(0);
       }
    }
    sparseVars.end();
    sparseVals.end();

     

  • Industrial88
    Industrial88
    8 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-29T16:56:31Z  

    I am not clear about what you mean that there are 3 sets of extreme directions in your feasibility cut.

    Anyway, function getRay() will only return one single ray for a problem instance. Calling it multiple times will always return the same ray.

    I am not sure but maybe this can help you: Assuming that all your variables are stored in an IloNumVarArray y then the following code produces a dense ray vector, the elements of which are in 1:1 correspondance to y (note that the code is simple but not efficient):

    IloNumArray sparseVals(env);
    IloNumVarArray sparseVars(env);
    cplex.getRay(sparseVals, sparseVars);
    IloNumArray ray(env);
    for (IloInt j = 0; j < y.getSize(); ++j) {
       // Find the value for y[j] in the ray (if any)
       bool found = false;
       for (IloInt k = 0; k < sparseVars.getSize(); ++k) {
          if ( y[j].getId() == sparseVars[k].getId() ) {
             ray.add(sparseVals[k]);
             found = true;
             break;
          }
       }
       if ( !found ) {
          // Variable y[j] not found -> zero coefficient in ray
          ray.add(0);
       }
    }
    sparseVars.end();
    sparseVals.end();

     

    Many thanks Daniel.

    Actually, I did the following procedure in order to assign each ray to the corresponding coefficient in feasibility cut.

      IloNumVarArray sparseVar(env);
      IloNumArray sparseVal(env);
      cplex.getRay(sparseVal, sparseVar);

       for (int h = 0;  h < sparseVar.getSize();  h++){
             for (i = 0; i < y.getSize(); i++){
                  if (sparseVar[h].getId() == y[i].getId()){
                      y_price[i] = sparseVal[h];}
             }

    }

    Where "y_price" is kind of "IloNumArray" parameter related to the decision variable "y"., i.e., IloNumArray y_price(env, y.getSize()).

    Is this way of definition is true?

    Updated on 2013-11-29T16:57:13Z at 2013-11-29T16:57:13Z by Industrial88
  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-29T17:16:45Z  

    Many thanks Daniel.

    Actually, I did the following procedure in order to assign each ray to the corresponding coefficient in feasibility cut.

      IloNumVarArray sparseVar(env);
      IloNumArray sparseVal(env);
      cplex.getRay(sparseVal, sparseVar);

       for (int h = 0;  h < sparseVar.getSize();  h++){
             for (i = 0; i < y.getSize(); i++){
                  if (sparseVar[h].getId() == y[i].getId()){
                      y_price[i] = sparseVal[h];}
             }

    }

    Where "y_price" is kind of "IloNumArray" parameter related to the decision variable "y"., i.e., IloNumArray y_price(env, y.getSize()).

    Is this way of definition is true?

    Yes, that looks correct. You just swapped the loops from my example.

  • Industrial88
    Industrial88
    8 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-29T17:21:08Z  

    Yes, that looks correct. You just swapped the loops from my example.

    Thanks.

    One more question! What is your recommendation to make it efficient?

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-11-29T18:18:47Z  

    Thanks.

    One more question! What is your recommendation to make it efficient?

    Use a std::map<IloInt,IloInt> in which the keys are the values of getId() and the values are the indices of the variables in y. Initialize that map in the beginning (when you setup y). Then have an array (y_price) that is all zeroed out. After calling getRay() go through the non-zeros as before. Instead of looping through y just look up the indices in the map and update y_price. When you are done with y_price then go through the ray's non-zeros again and zero out the respective slots in y_price so that is again all-zero for the next iteration.

  • Industrial88
    Industrial88
    8 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-12-01T19:29:21Z  

    Use a std::map<IloInt,IloInt> in which the keys are the values of getId() and the values are the indices of the variables in y. Initialize that map in the beginning (when you setup y). Then have an array (y_price) that is all zeroed out. After calling getRay() go through the non-zeros as before. Instead of looping through y just look up the indices in the map and update y_price. When you are done with y_price then go through the ray's non-zeros again and zero out the respective slots in y_price so that is again all-zero for the next iteration.

    Hello Daniel,

    There is a quick question come in my mind! When one exports his/her optimization model to an  ".lp" file, Cplex assigns a unique number to each decision variable in the ".lp" file. On the other hand, once one intends to return each decision variable ID though "getId()" function, he/she notices that ID of a given decision variable  is different from the number of that decision variaible in the ".lp" file. Is this usual or those ID and numbers should be the same? I carried some experiments for different problems and observed that they are not the same number.

    Thank you in advance for your consideration.

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Getting unbounded direction in C++ API

    ‏2013-12-02T06:32:29Z  

    Hello Daniel,

    There is a quick question come in my mind! When one exports his/her optimization model to an  ".lp" file, Cplex assigns a unique number to each decision variable in the ".lp" file. On the other hand, once one intends to return each decision variable ID though "getId()" function, he/she notices that ID of a given decision variable  is different from the number of that decision variaible in the ".lp" file. Is this usual or those ID and numbers should be the same? I carried some experiments for different problems and observed that they are not the same number.

    Thank you in advance for your consideration.

    Strictly speaking, CPLEX assigns a unique name to each decision variable. This name just happens to be x1, x2, ... The names that CPLEX creates are completely unrelated to the extractable ids returned by getId().

    If you want to find back your decision variables in the LP file then you should assign a name to your IloNumVar instances. There are at least 3 ways to do that:

    1. Use an IloNumVar constructor that accepts a 'char const *name' argument.
    2. Use IloNumVar::setName() to assign a name.
    3. Use IloNumVarArray::setNames() to set the name of all variables in an array.