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

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
    110 Posts
    ACCEPTED ANSWER

    Re: Getting unbounded direction in C++ API

    ‏2013-11-25T17:06:37Z  in response to Industrial88

    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
      ACCEPTED ANSWER

      Re: Getting unbounded direction in C++ API

      ‏2013-11-25T17:33:16Z  in response to DanielJunglas

      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
        ACCEPTED ANSWER

        Re: Getting unbounded direction in C++ API

        ‏2013-11-26T06:53:35Z  in response to Industrial88

        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
          110 Posts
          ACCEPTED ANSWER

          Re: Getting unbounded direction in C++ API

          ‏2013-11-26T07:05:16Z  in response to hllsen

          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
            ACCEPTED ANSWER

            Re: Getting unbounded direction in C++ API

            ‏2013-11-26T17:57:51Z  in response to DanielJunglas

            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
              110 Posts
              ACCEPTED ANSWER

              Re: Getting unbounded direction in C++ API

              ‏2013-11-29T15:28:23Z  in response to Industrial88

              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
                ACCEPTED ANSWER

                Re: Getting unbounded direction in C++ API

                ‏2013-11-29T16:56:31Z  in response to DanielJunglas

                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
                  110 Posts
                  ACCEPTED ANSWER

                  Re: Getting unbounded direction in C++ API

                  ‏2013-11-29T17:16:45Z  in response to Industrial88

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

                  • Industrial88
                    Industrial88
                    8 Posts
                    ACCEPTED ANSWER

                    Re: Getting unbounded direction in C++ API

                    ‏2013-11-29T17:21:08Z  in response to DanielJunglas

                    Thanks.

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

                    • DanielJunglas
                      DanielJunglas
                      110 Posts
                      ACCEPTED ANSWER

                      Re: Getting unbounded direction in C++ API

                      ‏2013-11-29T18:18:47Z  in response to Industrial88

                      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
                        ACCEPTED ANSWER

                        Re: Getting unbounded direction in C++ API

                        ‏2013-12-01T19:29:21Z  in response to DanielJunglas

                        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
                          110 Posts
                          ACCEPTED ANSWER

                          Re: Getting unbounded direction in C++ API

                          ‏2013-12-02T06:32:29Z  in response to Industrial88

                          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.