Originally posted by: SystemAdmin

[keepwalking said:]

I have a question about IloCplex::getRay in Concert Technology.

Now, I use getRay to get extremal rays from a continuous linear programming problem. But I can't get the right numbers of rays, they are less than the variables in my problem. I called this function like this:
IloNumArray tempExRays(env, Vars_Num);
cplex.getRay(tempExRays, All_Vars);
All_Vars denots the variables array (one dimension) in my problem, Vars_Num denotes the numbers of variables.

I have tried to use another function CPXgetray in Callable Library, it is right for my problem.
So I want to know if there are some special settings about getRay or I have some errors in calling it?
Thank you very much in advance.

P.S. The version of my cplex is 11.2.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[DanielJunglas said:]

The two methods slightly differ in the way the return the unbounded direction.
Assume the variables are x, y, and z and the unbounded direction is (1,0,3).
CPXgetray() returns the direction as dense vector [1.0,0.0,3.0] in its last
argument.
IloCplex::getRay() returns the direction as sparse vector in the two arrays
passed to it. That is, it returns only the variables that have non-zero
coefficients in the unbounded direction. In the above case it would return
[1.0,3.0] and [x,z] from which you can conclude that the unbounded
direction is (x,y,z)=(1.0,0.0,3.0).
So if the unbounded direction contains at least 1 zero IloCplex::getRay()
returns less variables than the model has.
This is also described in the API reference documentations.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[keepwalking said:]

Thank you very much for your help.

I would like to ask you another question.
How can we identify which variables have non-zero coefficients in the unbounded direction?
Thank you.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[DanielJunglas said:]

I don't really get the question. Do you want to determine these variables
before or after you call getRay()? If you do the following

IloNumArray vals(env);
IloNumVarArray vars(env);
cplex.getRay(vals, vars);

then CPLEX will resize arrays vals and vars appropriately and upon return
of getRay() the array vars will hold exactly those variables that have a non-zero
coefficient in the unbounded direction.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: keepwalking

Thank you for all your help to me.
I sent a message to you, but I didin't know if you had got it because this forum was updated during the past several days. So I propose my question to you again.

Last time, you told me as follows.
"I don't really get the question. Do you want to determine these variables before or after you call getRay()? If you do the following Code:
IloNumArray vals(env); IloNumVarArray vars(env); cplex.getRay(vals, vars);
then CPLEX will resize arrays vals and vars appropriately and upon return of getRay() the array vars will hold exactly those variables that have a non-zero coefficient in the unbounded direction."

I know what you mentioned. Actually, my question is:
After I used getRay(), I can get some variables which have non-zero coefficients in the unbounded direction. But I didn't know which decision variables (in the objective function) correspond to the variables with non-zero coefficients.

In addition, it is possible that CPXgetray() and getRay() obtain different extremal rays when they are used to solve the same problem?

Thank you.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm back on the forum, sorry for the delay.
First the easy one: I guess that behind the scenes IloCplex::getRay() invokes
CPXgetray() so the results should be the same. Do you observe otherwise?

I still don't get your question about which variables that getRay() returns
are in your objective function. In a sense all variables in the model are in
the objective function but some may have a coefficient of 0 there.
Consider this example:

IloEnv env;
 
      IloNumVar x(env, 0, IloInfinity, "x");
      IloNumVar y(env, 0, IloInfinity, "y");
      IloNumVar z(env, 0, IloInfinity, "z");
 
      IloModel model(env);
      model.add(IloRange(env, 0, 3 * x - 1 * z, 0));
      model.add(IloRange(env, 0, y, IloInfinity));
      model.add(IloMinimize(env, -1 * x));
 
      IloCplex cplex(model);
      cplex.setParam(IloCplex::PreInd, 0);
      cplex.solve();
 
      IloNumArray vals(env);
      IloNumVarArray vars(env);
      cplex.getRay(vals, vars);
 
      for (int i = 0; i < vars.getSize(); ++i)
         std::cout << i << ", " << vals[i] << " [" << vars[i].getName() << "]"
                   << std::endl;

It prints

0, 1 [x]
      1, 3 [z]

So the returned array holds variables x and z. So what additional
information do you want to get from CPLEX?
Can you give a small example to illustrate your question?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: keepwalking

Thank you for showing me this example.
In some simple example, I can not find my problem.
Could you give me your email?
I want to send you my code and my data file.
Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

My email is daniel dot junglas at de dot ibm dot com.
Please try hard to explain what the problem is ;-)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: keepwalking

Thank you very much.
I will send a email to you later and explain my question clearly.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I also find it very annoying when you invoke getRay() but it only returns some nonzero values without any 1-1 correspondence between the index of variables and the values in the array returned by the getRay().
I personally need to know for which variables the values appeared in the returned ray array is non-zero.

Even though there is way around it but that only increases the likehood of incorporating some risk in the code.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't understand the issue. cplex.getRay() does provide a sparse representation of the ray, i.e., a set of non-zero coefficients and a corresponding set of variables. Those two vectors map 1-to-1.
Concert is not an indexed based interface. If you want to have an indexed based interface then you are probably better off using the C API, even if your own code is C++. If you still want to have indices and Concert at the same time, then I think you need to use a map to map variables to indices, and an array to map indices to variables.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Tobias,

I understand how it works but there something which seems odd to me.
I have an instance x of IloNumVarArray which stored all the variables. As soon as I pass it together with an empty instance of IloNumArray to cplex.getRay(), it removes from x all variables x[i] except those participate in the ray with non-zero values. They are no longer available.

I am just confused about the connection between removing those variables and the non-indexing structure of concert.

I have been dealing with this for years by using maps -- same as what you suggest-- but I was always waiting for a solution from ILOG.

Calling the C interface inside the C++ code does not seem to be the most efficient way specially when one is trying to solve $n^2$ problems with this behaviour.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you observe is the correct and documented behavior of IloCplex::getRay().
Please refer to the documentation here. It clearly states that the arrays will be overwritten. If you don't want your array to get overwritten then just use a new array:

IloNumVarArray rayVars(env);
IloNumArray rayVals(env);
cplex.getRay(rayVals, rayVars);
// Now rayVals/rayVars contain the sparse representation of the ray.
std::cout << "Non-zeroes in the ray: << std::endl;
for (IloInt i = 0; i < rayVars.getSize(); ++i)
   std::cout << " " << rayVars[i] << " = " << rayVals[i] << std::endl;
// Do whatever you want with the ray.
...
// Release the temporary arrays.
rayVals.end();
rayVars.end();

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Many Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

As Daniel already answered: the point is that both arrays that you pass to getRay() are output-only parameters. It seems that you are looking for a method to which you can pass in a vector of variables and the method will provide you a corresponding vector of ray coefficients. But this is not how getRay() works.

I don't see your point about efficiency reasons to not use the C API. Clearly, you need to decide which API you use. You cannot mix them in a reasonable way. But if you use solely the C API from within your C++ application, performance should even get slightly better because you are getting rid of the overhead introduced by the Concert layer. Of course, then you may need to do some of the model management yourself.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Tobias.
--"You cannot mix them in a reasonable way"
In fact, I read your text differently and thought you are talking about a mix usage of both interfaces that is why it sound a bit strange. Now I got your point which is the sole use of C interface. Thanks again.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: IBM ILOG Blogger

This is just a test. Please ignore.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

My problem is something similar to the problem on Extreme Rays already discussed here, but more complicated.
I have two types of variables, say X and Y. Both are multidimensional. Let's say both are 2-dimensional arrays.
If I use cplex.getRay(vals, vars) to obtain the Extreme Ray, then vals and vars are required to be declared as single dimensional
arrays. In such a case, how would I know which values in vals are for X variables and which ones are for Y variables?

I am stuck on this for a week now, and would very much appreciate any help.

Thanks and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

what about using maps and hash_maps? doesn't that make the things easier?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks for your reply.
Would you mind elaborating a little bit.
I am unfamiliar with maps and hash_maps.

Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

IloNumVar is a subclass of IloExtractable, hence you can use IloExtractable::setObject():

• Use setObject() to attach to each IloNumVar instance the information whether it is an X or a Y variable (and maybe even the indeces into the X and Y arrays).
• Call getRay().
• Use getObject() to map the returned variables to the X and Y arrays.

Alternatively, use a map as Shahin suggested. For example, you could define

#include <map>
struct VariableInformation {
   // This structure defines all the data that is required to tell
   // whether a variable is in X or Y
};
std::map<IloInt,VariableInformation> info;
 
// For each variable 'var' add an entry in the map.
for ( ... )
   info[var.getId()] = VariableInformation(...)
 
// Now invoke getRay() and use the 'info' map
// to figure out whether the returned variables are in X or Y.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thank you very much for the prompt help.
I have been unable to glean much information regarding the usage of setObject() and getObject().
Could you please explain what you have suggested through a small example?
Let's assume there are 2 types of variables X and Y. Further assume that both X and Y are 1-dimensional arrays
such that X = x1, x2 and Y = y1, y2, y3 or any other suitable array of your choice.
For this example, could you please suggest how to use setObject() and getObject(), and how
to use these to map the variables returned by getRay() back to X and Y?

Thank you and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Here are two code snippets to illustrate my suggestions.
First a very simple one. It just uses setObject()/getObject() to mark variables as members of X or Y:

IloEnv env;
 
// Create arrays of variables. For sake of brevity I assume that
// variables have the same bounds 0 and 1.
IloNumVarArray X(env, 2, 0, 1); // X = { x1, x2 }
IloNumVarArray Y(env, 3, 0, 1); // Y = { y1, y2, y3 }
 
// Mark the variables.
IloAny markX = (IloAny)1;
IloAny markY = (IloAny)2;
for (IloInt i = 0; i < X.getSize(); ++i)
   X[i].setObject(markX);
for (IloInt i = 0; i < Y.getSize(); ++i)
   Y[i].setObject(markY);
 
...
 
// Invoke getRay().
IloNumVarArray rayVar(env);
IloNumArray rayVal(env);
cplex.getRay(rayVal, rayVar);
 
// Analyze the return value.
for (IloInt i = 0; i < rayVar.getSize(); ++i) {
   double val = rayVal[i];
   IloNumVar var = rayVar[i];
   if ( var.getObject() == markX ) {
      // Do what needs to be done for a variable from X.
      std::cout << "Value for X variable " << var << ": " << val << std::endl;
   }
   else if ( var.getObject() == markY ) {
      // Do what needs to be done for a variable from Y.
      std::cout << "Value for Y variable " << var << ": " << val << std::endl;
   }
}
 
...
 
env.end();

And here is a more sophisticated example that not only stores the type of the variable but also its index in the array:

IloEnv env;
typedef enum { ISX, ISY } vartype;
 
// Structure that encodes variable type and index.
struct Info {
   vartype type;
   IloInt const idx;
   Info(vartype t, IloInt i) : type(t), idx(i) {}
};
 
// Create arrays of variables. For sake of brevity I assume that
// variables have the same bounds 0 and 1.
IloNumVarArray X(env, 2, 0, 1); // X = { x1, x2 }
IloNumVarArray Y(env, 3, 0, 1); // Y = { y1, y2, y3 }
 
// Store variable type and index with each variable. 
for (IloInt i = 0; i < X.getSize(); ++i)
   X[i].setObject((IloAny)new Info(ISX, i));
for (IloInt i = 0; i < Y.getSize(); ++i)
   Y[i].setObject((IloAny)new Info(ISY, i));
 
...
 
// Invoke getRay()
IloNumVarArray rayVar(env);
IloNumArray rayVal(env);
cplex.getRay(rayVal, rayVar);
 
// Analyze the return value
for (IloInt i = 0; i < rayVar.getSize(); ++i) {
   double val = rayVal[i];
   IloNumVar var = rayVar[i];
   Info const *info = (Info *)var.getObject();
   switch (info->type) {
   case ISX:
      // 'var' is the same as X[info->idx].
      if ( var.getId() != X[info->idx].getId() )
         std::cerr << "Something went wrong!" << std::endl;
      else
         std::cout << "Value for X[" << info->idx << "]:" << val << std::endl;
      break;
   case ISY:
      // 'var' is the same as Y[info->idx].
      if ( var.getId() != Y[info->idx].getId() )
         std::cerr << "Something went wrong!" << std::endl;
      else
         std::cout << "Value for Y[" << info->idx << "]:" << val << std::endl;
      break;
   }
}
 
...
 
// At some point you would have to delete the Info objects
// stored with the variables.
 
...
 
env.end();

Note that yet another solution would be to encode all this information in the variable name and then just parse the names of the variables returned by getRay().
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thank you so much for your prompt help.

I have tested the first implementation, and it works just fine.
But, I need the second implementation (with proper mapping for the indices of different variables)
for my problem. I am going to try that now.

Thanks and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

I have already verified that your first suggestion works absolutely fine.
I am yet to try your second suggestion, but I am sure that will also work.
I have instead taken a different approach for my problem. Let me explain this using
the same small example with 2 types of variables X and Y such that X = x1, x2 and Y = y1, y2, y3.
Let the problem be:
Min aX + bY
s.t.: AX + BY >= C
x1, x2, y1, y2, y3 >= 0
When the problem is unbounded, then re-solving the above model with a small modification (make C = 0
and add a constraint: x1+x2+y1+y2+y3 = 1) will give us a solution, which is actually the extreme ray.
We can obtain the values by using, cplex.getValues(), which obviates the need for mapping the variables.

Obviously, the price one has to pay here is that one needs to solve one more optimization problem.
With variables mapping, one can obtain the extreme ray using getRay() without the need to solve one more problem.

Of course, with my proposed approach, we do not actually need to solve the modified problem (make C = 0
and add a constraint: x1+x2+y1+y2+y3 = 1) to optimality to get the extreme ray. What we need is
just any feasible solution to this modified problem.

So, my question is: How can we get any feasible (not necessarily optimal) solution to a problem
using cplex? I think the solver should be able to find any one feasible solution much faster.

Thanks and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> sjayaswal wrote:

> So, my question is: How can we get any feasible (not necessarily optimal) solution to a problem
> using cplex? I think the solver should be able to find any one feasible solution much faster.

One way is to set the objective function to a constant (say 0); then all feasible solutions are optimal, so the first feasible solution is the winner.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks Paul!

I have another related query:
Let me try to explain this with respect to the same small example:
Min aX + bY
s.t.: AX + BY >= C

where X = x1, x2 and Y = y1, y2, y3.
x1, x2, y1, y2, y3 >= 0

Let's say that this problem appears as a subproblem in Bender's decomposition.
So, one needs to solve a similar problem repeatedly.
When the problem is unbounded, then one way to get its extreme rays is using cplex.getRay().
But in this case, one needs to map the returned values since getRay() returns a sparse vector.
A different approach that I am currently using, which obviates the need for variable mapping, is to
solve the following modified problem:

Min aX + bY (or any arbitrary objective)
s.t.: AX + BY >= 0
x1+x2+y1+y2+y3 = 1
x1, x2, y1, y2, y3 >= 0

cplex.getValues() in this case gives the extreme ray for the original problem.

My question is the following:

1. Does getRay() also use the same technique (i.e., solve a modified optimization problem) to get the extreme rays?
2. If getRay() does something different to obtain the extreme rays, which of the two approaches (1. use getRay(); 2. solve a modified optimization problem) is more efficient?

Thanks and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> sjayaswal wrote:
> I have another related query:
> Let me try to explain this with respect to the same small example:
> Min aX + bY
> s.t.: AX + BY >= C
>
> where X = x1, x2 and Y = y1, y2, y3.
> x1, x2, y1, y2, y3 >= 0
>
> Let's say that this problem appears as a subproblem in Bender's decomposition.
> So, one needs to solve a similar problem repeatedly.
> When the problem is unbounded,

Sorry, you lost me here. In Benders decomposition (at least as I understand it), a subproblem should never be unbounded. If the subproblem is unbounded for any feasible solution to the master problem, then the original problem is unbounded.

Do you mean that this is the dual of the actual subproblem?

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks Paul for pointing this out.
Yes, I did mean dual of the subproblem.
Now, back to my original question, any help/suggestion is very much appreciated.

Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

So the objective function of your modified problem will be the same function that would have been the objective of the dual to the subproblem (i.e., the RHS of the primal subproblem, based on the current master problem solution)? Do you intend to solve the unhacked dual first, and solve the hacked one only if the unhacked dual is unbounded? Or go the other way, solve the hacked version first and, if its objective value is zero (signaling that the primal subproblem is feasible), then solve the unhacked dual? Or (third possibility) are you doing a problem where all you need to know is feasibility of the subproblem (there are no optimality cuts), in which case you only need to solve the hacked dual?

As to question #1 (is this how getRay works), I'm not privy to the secrets of CPLEX's plumbing, but I suspect not. I believe that CPLEX solves the subproblem as given and, if it detects an unbounded solution, constructs the ray from the information that told it the problem was unbounded.

As to question #2 (which is more efficient), if your subproblem can generate both optimality and feasibility cuts for the master, then I'm pretty certain that using getRay is preferable, since you only have to solve one subproblem per iteration. If you will only get feasibility cuts, then I'm not certain, and in fact it may not make much difference. The key is that you will be making the same change to the objective function at each Benders iteration, and that change may result in a few incremental simplex pivots or a lot of additional pivots. I don't think the number of additional pivots will vary much. Adding one normalizing constraint would not seem to change the cost per simplex iteration all that much. Whether fetching the solution to the hacked problem is faster or slower than fetching the ray using getRay is also something that I can't predict.

You seem to be motivated here by avoiding the mapping necessary to work with getRay. If your problem is large (and assuming things are sparse), that mapping might actually work to your advantage. The call to getRay will return only a hopefully small number of nonzero terms, and those are the only terms you need in your feasibility cut. With your modified approach you have to fetch and then loop through all the dual variables to construct your cut.

Hope that helps,
Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks a lot Paul for your detailed response, and my apologies for the delay in getting back:
I was trying a few ideas before I could get back. Below are my responses:

1.] So the objective function of your modified problem will be the same function that would have been the objective of the dual to the subproblem (i.e., the RHS of the primal subproblem, based on the current master problem solution)?

Ans.] The objective function of the modified problem may be the same but need not be.
The extreme ray is just any feasible (and not necessarily optimal) solution to the modification of the dual of the subproblem.

2.] Do you intend to solve the unhacked dual first, and solve the hacked one only if the unhacked dual is unbounded? Or go the other way, solve the hacked version first and, if its objective value is zero (signaling that the primal subproblem is feasible), then solve the unhacked dual? Or (third possibility) are you doing a problem where all you need to know is feasibility of the subproblem (there are no optimality cuts), in which case you only need to solve the hacked dual?

Ans.] I use option 1: solve the unhacked dual first, and solve the hacked one only if the unhacked dual is unbounded.

3.] You seem to be motivated here by avoiding the mapping necessary to work with getRay. If your problem is large (and assuming things are sparse), that mapping might actually work to your advantage. The call to getRay will return only a hopefully small number of nonzero terms, and those are the only terms you need in your feasibility cut. With your modified approach you have to fetch and then loop through all the dual variables to construct your cut.

Ans.] Very true. I was initially scared to try the mapping of variables as it looked complicated, but after implementing it, I realize it is a better way to do it. Moreover, with the "hacked" problem, I was running into some problems. Let me explain this problem using an example. Let say the dual of the subproblem is as below:

Min aX + bY
s.t.: AX + BY >= C

where X = x1, x2 and Y = y1, y2, y3.
x1, x2, y1, y2, y3 >= 0

If this turns out to be unbounded, then the dual of the hacked problems we solve is:

Min aX + bY (or any arbitrary objective)
s.t.: AX + BY >= 0
x1+x2+y1+y2+y3 = 1
x1, x2, y1, y2, y3 >= 0

This works fine. But, I have the dual of the subproblem in which some of the variables are negative/free, i.e.,

Min aX + bY
s.t.: AX + BY >= C

where X = x1, x2 and Y = y1, y2, y3.
x1 >=0, x2<=0, y1 free, y2<=0, y3 >= 0

In such cases, adding the normalization constraint (x1+x2+y1+y2+y3 = 1) occasionally makes the problem infeasible. In such cases, for some problems, I was still able to solve them by using a slightly different normalization constraint (x1+x2+y1+y2+y3 = -1). This worked purely by chance, and I am never sure apriori what constant to use in the RHS of the normalization constraint. All such problems get circumvented by using getRay().

Thanks a lot!
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Continuation of my response to http://1.:

1.] So the objective function of your modified problem will be the same function that would have been the objective of the dual to the subproblem (i.e., the RHS of the primal subproblem, based on the current master problem solution)?

Ans.] The objective function of the modified problem may be the same but need not be.
The extreme ray is just any feasible (and not necessarily optimal) solution to the modification of the dual of the subproblem. So, any function in the objective is fine. One may even use a constant like 0 or 1 in the objective function.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> sjayaswal wrote:
> Continuation of my response to http://1.:
>
> 1.] So the objective function of your modified problem will be the same function that would have been the objective of the dual to the subproblem (i.e., the RHS of the primal subproblem, based on the current master problem solution)?
>
> Ans.] The objective function of the modified problem may be the same but need not be.
> The extreme ray is just any feasible (and not necessarily optimal) solution to the modification of the dual of the subproblem. So, any function in the objective is fine. One may even use a constant like 0 or 1 in the objective function.

Actually, I'm not convinced this is true (nor that your hacked subproblem necessarily generates a ray).

Suppose that the dual to the (infeasible) subproblem has two variables (y1 >= 0, y2 >= 0) and the single constraint y2 <= 1 (so the feasible region is a rectangular strip unbounded in the y1 direction). If you add the constraint y1 + y2 = 1, the feasible region is the unit simplex. With a constant objective function, y = 0 is the likely optimal solution, which is unhelpful. With a nonconstant objective function, even the original dual objective, it's possible that y = (0,1) is the optimal solution; but that is not a recession direction for the dual.

Assuming the dual variables are nonnegative, maximizing c'y for some c >> 0 (strictly positive in all components) and adding the constraint y1 + ... + yn <= K for sufficiently large K would work ... but I'm not sure how you would know an appropriate value of K.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks Paul for taking time to think through this. This is certainly helping me understand things much better.

The hacked subproblem should always give an extreme ray. Let me rewrite a simple unhacked and hacked dual subproblem once again. Please correct me if any of the following steps is incorrect.

Let the unhacked (original) dual subproblem be:
Min aX + bY
s.t.: AX + BY >= C

where X = x1, x2 and Y = y1, y2, y3.
x1, x2, y1, y2, y3 >= 0

If this turns out to be unbounded, then the dual of the hacked subproblem we solve is:

Min aX + bY
s.t.: AX + BY >= 0
x1+x2+y1+y2+y3 = 1
x1, x2, y1, y2, y3 >= 0

Please note that the RHS in the hacked problem is 0, apart from the addition of a normalization constraint.

Now, let's turn to your example:

Suppose that the dual to the (infeasible) subproblem has two variables (y1 >= 0, y2 >= 0) and the single constraint y2 <= 1 (so the feasible region is a rectangular strip unbounded in the y1 direction). If you add the constraint y1 + y2 = 1, the feasible region is the unit simplex.

What you have missed here is the fact that the RHS in the hacked problem is 0. So, the feasible region of the hacked subbproblem is now represented by the following constraints:
y2 <= 0
y1+y2=1
y1>=0, y2>=0

Clearly, the feasible region to the problem is not a unit simplex but the point (1,0).
So, the solution to the hacked subproblem in this case should give the correct Extreme Ray.

This method of obtaining Extreme Rays is explained in "Linear programming & Network Flows by Bazaraa, Jarvis & Sherali, chapter 2.

Please correct me if I am missing something.

Thanks and Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You're correct: the first time I looked at your hacked dual subproblem, I noticed that you had switched to the constraints defining the recession cone, but when I came back to it I missed that and thought you were adding the bounding constraint to the original dual. The hacked dual will in fact give you one of the recession directions. I'm still not sure it's worth the extra work, though.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sjayaswal

Thanks Paul!
Yes, I do agree with you: getRay() with variable mapping, as suggested on this forum, seems to be a better way of working with Extreme Rays.

Regards,
Sachin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: PabloMunhoz

Hello everyone!!!

Sorry for reopen this Topic, but there is no better option today for solve this problem? I already read a lot , but I think this is the only solution.

Thanks,

Pablo

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SOPHIA__

hi, i want to ask how do you code for the multidimonstional variables? Can you post your code here? Thank you for your reply. 

#CPLEXOptimizers
#DecisionOptimization

One way to do this for a 2-dimensional array x[][] is as follows:

Define a class Index that will store for each variable the first and second index:

struct Index {
   IloInt i; // Index in first dimension
   IloInt j; // Index in second dimension
   Index(IloInt ii = -1, IloInt jj = -1) : i(ii), j(jj) {}
};

Next create a map that maps each variable to its indices in the x[][] array (IloNumVar::getId() returns a unique id for each variable):

   std::map<IloInt,Index> var2idx;
   for (IloInt i = 0; i < x.getSize(); ++i)
      for (IloInt j = 0; j < x[i].getSize(); ++j)
         var2idx[x[i][j].getId()] =  Index(i, j);

Now get the ray as flat vector from CPLEX:

   IloNumArray ray(env);
   IloNumVarArray flat(env);
   cplex.getRay(ray, flat);

Finally map the flat vector back to something two-dimensional:

   for (IloInt k = 0; k < flat.getSize(); ++k) {
      // Get the variable and its ray value from the flat vector.
      IloNumVar var = flat[k];
      double val = ray[k];
      // Get the Index information from the map. The variable stored in
      // 'var' is the same as 'x[idx.i][idx.j]'.
      Index idx = var2idx[flat[k].getId()];

      // If you now have a two-dimension value array called ray2d then you
      // can for example do
      //    ray2d[idx.i][idx.j] = val
   }

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SOPHIA__

Thank you very much. I will try it . 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Job_Jonah

Hi, 

I am working on Benders Decomposition and I just came up with this threat. I pretty much understand how both algorithms work but I had hard time to implement the second one for multi-dimensional variables.

How can we extend the second method for multi-dimensional variables?

For example I have the variable X[i][j]. I would like to store the extreme dual ray values on Xray[c][i][j] where index c is for the iteration counter.

 

Thanks in advance.

Jonah.

#CPLEXOptimizers
#DecisionOptimization

Using setObject()/getObject() you can store for each variable the i and j index. With this you can easily map the values returned by getRay() into the Xray array.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Job_Jonah

Daniel,

Thank you so much for the response. I managed to get extreme dual rays for 2-dimensional variables if I have a 2-dimensional variable ( such as X[i][j]) and values return by getRay() is also 2-dimensional (such as Xray[i][j]). However in my case I have variable such as X[i][j] and extreme dual ray values  Xray[c][i][j] where index c is for the iteration counter. Therefore, I guess I have R2 to R3 mapping. So I get confused in the lines 2-9 and 16-20  in the second sophisticated algorithm. Also, how do you handle line 35 where we you have "case ISX"? Is it going to be "case Xray[c]"?

Could you please give an example if you do not mind?

Thank you so much.

Jonah

 

 

#CPLEXOptimizers
#DecisionOptimization

Sorry, I don't see where your problem is :-( Aren't the variables the same in each iteration? If so then the mapping is the same as well. And to adapt the code you just have to replace Xray[i][j] in the code by Xray[c][i][j] in the appropriate places, or not?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Job_Jonah

Daniel,

Thanks for the reply. I tried to the same way as you have recommended. I have replaced Xray[i][j] in the code by Xray[c][i][j] in the appropriate places however somehow it gives syntax problem. There might be issues in my code. I will go over it and let you know.

Thanks again.

 

#CPLEXOptimizers
#DecisionOptimization