2
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ You omitted the third constraint (corresponding to $y_3$) in your dual model. $\endgroup$
    – prubin
    Mar 10 at 16:36
  • $\begingroup$ Thanks @prubin, I have just added this. $\endgroup$
    – Kit Searle
    Mar 13 at 14:12

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
5
  • $\begingroup$ Thanks @prubin your answer. This now makes much more sense to me. To clarify my third question, I am unsure of the ordering which dual_farkas() will return the extreme ray because we do not pass the function any arguments. Would the first element in farkasConstraints correspond to c1 and the second element correspond to c2? I have a follow up on your response to my fourth question: I see that the two rays are the same, but when using them to generate benders feasibility cuts can we say that the extreme ray returned by cplex or xpress provide stronger cuts? $\endgroup$
    – Kit Searle
    Mar 13 at 14:33
  • $\begingroup$ I'm not positive, but I don't think the order of the constraints in the farkasConstraints object is necessarily the order they appear in the original model. You need to go through it, identify which constraint each element is, and associate the corresponding entry in farkasValues with that constraint. I did this in an old blog post (orinanobworld.blogspot.com/2010/07/…), albeit in Java. $\endgroup$
    – prubin
    Mar 13 at 15:51
  • $\begingroup$ It's possible things have changed with recent versions of CPLEX, but if you could assume that dual_farkas() returned one multiplier for every constraint in the order the constraints were entered, there would be no need for the farkasConstraint object. $\endgroup$
    – prubin
    Mar 13 at 15:51
  • $\begingroup$ As for the feasibility cuts, they will be identical. If one is $a'x \ge b$ the other will be $2a'x \ge 2b.$ $\endgroup$
    – prubin
    Mar 13 at 15:53
  • $\begingroup$ Thank you for your help. It has been very useful to me! $\endgroup$
    – Kit Searle
    Mar 16 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.