Get the extreme ray from infeasible primal

ユーザーの入力を待っています。

Nicolas Zerega

2023年05月19日 15:53

• 
• 
• 

Dear all,

I'm currently solving a continuous model using the dual-simplex method with Python in order to obtain cuts that then have to be added to another MIP.

This model can be optimal or infeasible. In case it is optimal then I get the dual extreme point using the *.pi constraint attribute and can add the corresponding cut to my original problem.

When the primal is infeasible then I know that (in my case) the dual will always be unbounded and, I also know that there will always be, at least, one violated condition. Hence, I need to get an extreme ray for it and add the cut.

As I read here: https://support.gurobi.com/hc/en-us/community/posts/360076508331-Unbounded-ray-of-an-infeasible-LP-problem-Python-?input_string=Get%20the%20unbounded%20ray%20from%20infeasible%20primal

I could query FarkasDual() for each constraint in the primal and, supposedly, get a extreme ray of the dual but, in my case, the vector that I get is... weird. What I mean is that, the values I get from applying FarkasDual() tell me that there aren't any violated conditions, which isn't true.

In the docs it doesn't explicitly say that FarkasDual provides an extreme ray but I also read this blog from Paul Rubin https://orinanobworld.blogspot.com/2011/07/farkas-certificates-in-cplex.html  (although it's for CPLEX) in which, you could obtain an extreme ray for the dual based on the Farkas Certificate.

I would highly appreciate if you could provide a bit of light regarding this FarkasDual attribute

I implemented the dual of this problem to make sure that I get an extreme ray by using *.UnbdRay and that there is a violated condition. I confirmed both.

The issue with the dual is that it takes way too much time to generate and to solve, meanwhile the primal is very quick.

And so, I want to generate the column vector of every non-basic variable in the primal as to obtain a possible extreme ray of the dual without having to solve it directly.

Is there a way to access that information? For example, the last tableau.

Thank you very much!

Kind regards,

Nicolás

関連

• Attribute

0

• 

  Roland Wunderling

  • Gurobi Staff

  2023年05月24日 11:47

  I'm not sure I follow.  The Farkas Proof gives you a linear combination of constraints that cannot be feasible given the variable bounds.  It does not point to a single constraint with such a property.  Indeed, it is likely that every single constraint alone can be satisfied.  Even if there were, the Farkas Proof does not need to include it.

  0

サインインしてコメントを残してください。