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.
- How should I interpret the dual ray?
- Which cplex method is correct?
- What element of the extreme ray corresponds to which constraint?
- Why is the dual ray found using cplex different from the one returned by Xpress?
- If I solved the dual problem directly, how could I get the extreme ray?