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 -2*y - y>= 3) c2 = prob.add_constraint(-2*y - y>= 2) obj = y + y -2*y 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?