Originally posted by: zoldfish

Hi

I am using CPlex 12.1, Concert Technology. I have some problems on finding and using extreme rays.

1. Here is the FAQ I consult:

Link:http://www-01.ibm.com/support/docview.wss?uid=swg21400058

It says that if the primal problem is infeasible which is my situation and primal simplex optimizer is in use, I should use getDuals function. However, here is the description of method getDuals in the C++ API manual:

getDuals
public void getDuals(IloNumArray val, const IloRangeArray con) const
This method puts the dual values associated with the ranges in the array con into the array val. Array val is resized to the same size as array con, and val[i] will contain the dual value for constraint con[i].
Then how should I use this method to get extreme rays? Is it the situation that when the primal function is infeasiable when I use this method it will automatically give me the extreme ray instead of the dual solutions of the primal problem?

2.According to the link above, if the primal problem is infeasible and dual simplex optimizer is in use, then I can simply use getRay method to get extreme rays. I also wonder how should I use this method and what it will give me in return.

3.If the primal problem is unbounded naturally I can use getRay to get extreme rays. But here is the description of this method:

getRay
public void getRay(IloNumArray vals, IloNumVarArray vars) const
This method returns an unbounded direction (also known as a ray) corresponding to the present basis for an LP that has been determined to be an unbounded problem. CPLEX puts the the nonzero values of the unbounded direction into the array vals, and it puts the corresponding variables of the extracted model into the array vars.

I noticed that it only returns the nozero values of the direction instead of all values. If I am under this situation:
Primal problem has 3 variables x1, x2, x3, and this problem is proven unbounded. Then I use method getRay(IloNumArray vals, IloNumVarArray vars) and in result vars contains only x1 and x3, with their corresponding values in vals. If I want to calculate the numerical result of function x1+x2+x3, how should I write the code? The premise is that I don't know what variables will be nonzero before I call getRay. I am quite confused about this and I wish you chould help me.

I am a freshman to CPlex so these problems may seem too simple. Thank you for your warm reples!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RWunderling

getDual() and getRay() differ in that getDual() allows you to query dual values for specific constraints you
are interested in, while getRay() returns the full unbounded ray, because only the full vector is in fact the
unbounded direction. The data returned by getRay() is the vector in sparse format by populating the arrays
vals and vars in the following way: vals[i] it the coefficient of the ray vector for variable vars[i] for all
i, while all variables not added to vars have a coefficient of 0.

Hope this helps,

Roland
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: zoldfish

Thank you for your reply!

Can the following codes work to get the extreme ray?

//cplex is an instance of class IloCplex
//con is the constraints of the LP
cplex.solve();
IloNumArray ray(env);
if (cplex.getCplexStatus()==CPX_STAT_INFEASIBLE)     //the primal problem is infeasible
{
        cplex.getDuals(ray, con);
}

BTW, I am still confused that if the primal problem is infeasible and dual optimizer is in use, can the following codes give me the extreme ray?

//cplex is an instance of class IloCplex
cplex.setParam(IloCplex::RootAlg, IloCplex::Dual);
cplex.solve();
IloNumArray ray(env);
IloRangeArray con(env);
if (cplex.getCplexStatus()==CPX_STAT_INFEASIBLE)
{
        cplex.getRay(ray, con);                 //is it correct??
}

What's more the 4th problem I listed before also confuses me. That would be great if someone gives me some simple but detailed codes to show how to get it done.

Thanks a lot!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: zoldfish

Actually when the primal problem is infeasible and siplex optimizer is in use, the following codes don't work according to my attempt.

code
//cplex is an instance of class IloCplex
//con is the constraints of the LP
cplex.solve();
IloNumArray ray(env);
if (cplex.getCplexStatus()==CPX_STAT_INFEASIBLE) //the primal problem is infeasible
{
cplex.getDuals(ray, con);
}

code

Instead an exception would be caught saying
ERROR: CPLEX error 1217: No solution exists.
This exception is thrown when method getDuals() is executed.

What should I do?
Thank you for your warm replies!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Are you looking for an extreme ray of the primal or of the dual? If the primal is unbounded, it has one or more extreme rays. If the primal is infeasible, it has not extreme rays but the dual probably does. (I say "probably" because it is technically possible for both primal and dual to be infeasible, but it is typical that an infeasible primal has an unbounded dual.) Trying to find an extreme ray of an infeasible primal makes no sense.

Either way, getDuals does not locate a ray. getDuals returns an extreme point of the dual feasible region. getRay returns the direction vector for an unbounded ray.

/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: zoldfish

Thank you for your reply.

I am looking for the extreme ray of dual problem while the primal problem is infeasible.

According to this FAQ:

Link:http://www-01.ibm.com/support/docview.wss?uid=swg21400058

It says that

If you are using the primal simplex optimizer and the model is primal infeasible and dual unbounded, you can obtain the extreme ray for the dual problem through:
the routine CPXgetpi in the Callable Library (C API)
the methods getDuals in the C++ and Java APIs

However, I don't know how to use getDuals() to obtain extreme rays of the dual problem under this situation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't think the FAQ is entirely correct. The good news is that you can use getDuals if you first turn off the presolver. Here's some sample code (in Java, but C++ is quite similar):

cplex = new IloCplex();
// create two nonnegative numerical variables X & Y
IloNumVar[] x = new IloNumVar[2];
x[0] = cplex.numVar(0, Double.MAX_VALUE, "X");
x[1] = cplex.numVar(0, Double.MAX_VALUE, "Y");
// minimize 3x - 3y
cplex.addMinimize(cplex.scalProd(new double[] {3., -3.}, x));
// create two constraints
IloRange[] c = new IloRange[2];
// constraint C1: X - Y >= 1
c[0] = cplex.addGe(cplex.scalProd(new double[] {1., -1.}, x), 1, "C1");
// constraint C2: 2X + Y <= 0 (clearly incompatible with variable bounds
c[1] = cplex.addLe(cplex.scalProd(new double[] {2., 1.}, x), 0, "C2");
// turn off the presolver
cplex.setParam(IloCplex.BooleanParam.PreInd, false);
cplex.solve();
// verify primal is infeasible
System.out.println("CPLEX status: " + cplex.getCplexStatus());
// call getDuals
double[] duals = cplex.getDuals(c);
System.out.println("Dual solution: " + duals[0] + ", " + duals[1]);

And here is the output:

Iteration log . . .
Iteration:     1   Dual infeasibility =             0.000000
CPLEX status: Infeasible
Dual solution: 3.0, 0.0

The good news is that (3, 0) is in fact a feasible solution of the (unbounded) dual. The bad news is that it is not the direction vector of a dual ray. For instance, 2*(3, 0) = (6, 0) is not dual-feasible.

Here's a pointer to an old thread on sci.op-research: http://groups.google.com/group/sci.op-research/browse_thread/thread/18661906993fd3fb/21b12f2e5333305d?lnk=gst&q=dual+ray#21b12f2e5333305d. Back then, the best we could come up with to get an extreme dual ray was a two step process: (1) solve the primal and use getDuals to locate an extreme point of the dual feasible region; (2) solve the dual and use getRay to get the direction vector of a dual ray. If you just care about the direction and not the dual vertex where it's anchored, just the second step should work, but this requires formulating the dual.

/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: zoldfish

Thank you for your reply!

But do you mean that the only way to get the extreme ray of the dual problem is to fomulate the dual problem first? That's a bit troublesome...

BTW, here is the last problem...I am not very sure how to use method getRay().

For example, if the primal problem has 3 variables x1, x2, x3, and this problem is proven unbounded. Then I use method getRay(IloNumArray vals, IloNumVarArray vars) to get the extreme ray. However, this method only gives me the nonzero values of x1-x3. If I want to calculate x1+2*x2+3*x3, how should I write the code? The premise is that I don't know what variables will be nonzero before I call getRay. I am quite confused about this and I wish you chould help me.

Thank you again for your warm help!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> zoldfish wrote:
>
> But do you mean that the only way to get the extreme ray of the dual problem is to fomulate the dual problem first? That's a bit troublesome...

For an alternative approach, you might look at the last post in this thread: http://www.ibm.com/developerworks/forums/thread.jspa?messageID=14433103&tstart=0#14433103. The dualFarkas method gets you some of the information needed to construct a dual ray for an infeasible primal, but there is work to be done to complete the ray.
>
> BTW, here is the last problem...I am not very sure how to use method getRay().
>
> For example, if the primal problem has 3 variables x1, x2, x3, and this problem is proven unbounded. Then I use method getRay(IloNumArray vals, IloNumVarArray vars) to get the extreme ray. However, this method only gives me the nonzero values of x1-x3.

Just to be clear, those values are the nonzero entries of the direction vector of the ray. So if getRay returns (5, 2) in vals and (x1, x3) in vars, the ray has direction (5, 0, 2) in x-space (and can be anchored at any vertex of the feasible region).

> If I want to calculate x1+2*x2+3*x3, how should I write the code? The premise is that I don't know what variables will be nonzero before I call getRay. I am quite confused about this and I wish you chould help me.

If by x1 etc. you mean the values returned by getRay, just treat them like any vector of doubles.

/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: zoldfish

> Just to be clear, those values are the nonzero entries of the direction vector of the ray. So if getRay returns (5, 2) in vals and (x1, x3) in vars, the ray has direction (5, 0, 2) in x-space (and can be anchored at any vertex of the feasible region).
> If by x1 etc. you mean the values returned by getRay, just treat them like any vector of doubles.
>
> /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)

Thank you for your reply!

However, what I mean is that as getRay(IloNumArray vals, IloNumVarArray vars) only gives me the nonzero values it is difficult to deal with the results I got from this method in the code. For the example I listed before, if I write like this:

IloNumArray vals;
IloNumVarArray vars;
cplex.getRay(vals, vars);
IloNum result = vals[0]+2*val[1]+3*val[2];

Apparently it is incorrect, for x1, x2 or x3 may be zero. However before calling this method I don't know which variable will be zero so I must use the information vars gives me. How should the code be written? I am rather confused.

Your help will be of great help to me, thank you!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You're trying to take the scalar product of a vector with the ray's direction vector? One way is to use a loop to compare each original variable to the variables returned by getRay.

Assuming your original variables are in an IloNumVarArray named myVars and the vector you want to dot with the ray's direction is in double[n] v:

double product = 0;
for (i = 0; i < n; i++) {
  for (j = 0; j < vars.length; j++) {
    if (myVars[i] == vars[j]) {
      product += v[i]*vals[j];
      break;
    }
  }
}

That's Java code, but I think it's the same in C++ (give or take whether vars.length is the correct way to get the dimension of vars). If you plan to do the inner product of a number of vectors with the same ray direction vector, it might save time to use the STL map class to map each original variable to either its ray value or (if not in the ray) to zero.

/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: zoldfish

This is exactly what I need!

Thank you again for your warm help!
#CPLEXOptimizers
#DecisionOptimization