Farka's lemma

[enri07]

Hi everyone!

First of all, I just started to use HiGHS and I think you're doing an amazing job!

Now I was wondering if there is something like the CPLEX routine CPXdualfarkas, in order to obtain those y values for the rows. Can someone help me?

Thank you very much in advance.

Enrico Calandrini

[jajhall]

No, we don't give these values. What we do give is the dual ray y^TA, which seems to be what most people are after with a Farkas proof of infeasibility

[enri07]

Thank you for your fast response.

I understand, and there is no way of extracting y before y^T A is computed, right?

[enri07]

Ok, sorry to bother you but I looked better at the code and find out that the function Highs_getDualRay actually returns a vector of length num_row. I misundertood your message, because in the way it is written I thought that y^T A was a vector of length num_col.

I think this is exactly what i was looking for. Just to be clear, if we use this definition of dual ray:

The dual ray is a vector w of values that, if multiplied by a positive amount and added to any w1 feasible in the dual, produces another solution feasible in the dual.

the function Highs_getDualRay returns exactly w, am i correct?

Again, thank you for your time.

[jajhall]

Yes, looking at the code, HiGHS::getDualRay yields y, and this appears to be the accepted interpretation of "ray". However, it's the (dual simplex) ratio test with y^TA that identifies dual unboundedness, so that's why I think of it as the ray. Of course giving y is more useful, as y^TA is easily computed.