Obtaining the dual ray of an infeasible lp to generate a benders feasibility cut

Question

I am struggling to correctly interpret the meaning of a dual ray for an infeasible primal lp. Consider the following example. $$ \min z = y_1 + y_2 -2y_3 $$ s.t $$y_1 -2y_1 -y_3 \ge 3 $$ $$-2y_1 - y_2 >=2 $$ $$y_1, y_2, y_3 \ge 0$$ which has a dual $$\max w = 3u_1 + 2u_2$$ s.t. $$u_1 - 2u_2 \le 1$$ $$-2u_1 - u_2 \le 1$$ $$-u_2 \le -2$$ $$u_1, u_2 \ge 0.$$

In this case, the primal is clearly infeasible and the dual is unbounded (as expected). Now if I want to extract the extreme ray for this problem what should I do? If I solve the problem using docplex, turning off presolve and choosing the dual simplex with the following code:

prob = Model('infeasible')
y = prob.continuous_var_list(range(3), name = 'y', lb = 0)
c1 = prob.add_constraint(y[0] -2*y[1] - y[2]>= 3)
c2 = prob.add_constraint(-2*y[0] - y[1]>= 2)
obj = y[0] + y[1] -2*y[2]
prob.set_objective("min", obj)
prob.parameters.lpmethod = 2
prob.parameters.preprocessing.presolve = 0
sol=prob.solve(log_output = True)

The solver returns infeasible. Now I want to get the extreme ray for this problem. At this post they say that we should use the dualfarkas member function. If I do this as follows

farkasConstraints, farkasValues = prob.get_engine().get_cplex().solution.advanced.dual_farkas() 

I get that farkasConstraints = [1.0, 0.5] and farkasValues = 4, how should I interpret this? What is confusing me is that if I use

ray = prob.get_engine().get_cplex().solution.get_dual_values()

I get that ray = [2.0,0.5]. What is the difference between the two? To make things more confusing, if I solve the problem in Xpress and obtain the dual ray using the ray = prob.getdyalray() I get ray = [0.5, 0.25] which is exactly half what cplex returns. Does this mean that the dual ray is not unique? I summarize my questions as follows.

1. How should I interpret the dual ray?
2. Which cplex method is correct?
3. What element of the extreme ray corresponds to which constraint?
4. Why is the dual ray found using cplex different from the one returned by Xpress?
5. If I solved the dual problem directly, how could I get the extreme ray?

Answer 1

Technically, a recession direction is a vector $v$ such that if $w$ is feasible then so is $w+\lambda v$ for any $\lambda > 0,$ while a ray is a recession direction anchored at a specific point. Most people in optimization use the terms interchangeably (I think).

So to answer (some of) your questions ...

1. As I explained in the definition of recession direction, the dual ray is a vector of $w$ values that, if multiplied by a positive amount and added to any $\hat{w}$ feasible in the dual, produces another solution feasible in the dual. For instance, $(0,0)$ and $(2, 0.5)$ are feasible solutions to your dual and $(1, 0.5)$ is a recession direction. For any $\lambda > 0,$ both $(\lambda, 0.5\lambda)$ and $(2 + \lambda, 0.5 + 0.5\lambda)$ are feasible in the dual.
2. You are misinterpreting the vector $(2, 0.5).$ It is not a ray; it is a feasible solution to the dual. When solving the dual, CPLEX got to that corner of the dual feasible region and then discovered a direction along which the objective function improved forever, at which point it stopped and declared the problem unbounded.
3. I do not understand what you are asking here.
4. They are the same ray. One is just twice the other. The key is that they are pointing in exactly the same direction.
5. If you mean solving it by hand, using the simplex method, at some point you would obtain a tableau where the reduced costs pointed to a variable that wanted to enter the basis but the row selection criterion would fail to find a row in which to pivot. The pivot column would be a recession direction.