Hello,

I'm solving a LP, which I know is infeasible and its dual is unbounded. I just want to get one of the unbounded dual extreme rays.
I'm wondering if there is a neat method to obtain the dual extreme ray (which proves the infeasibility of the primal) when using the concurrent method as the root algorithm.

Since we cannot know upfront whether it is the primal or dual simplex proves the infeasibility, we cannot determine if we should use dualFarkas() or getDuals(). I understand it is workable to use try-catch framework (in C++), but just want to know if there is any other option to deal with this.

A possible way I currently have in my mind is that we explicitly feed the dual formulation of the problem to the solver, and in this case, no matter it is the primal or dual simplex proves the unboundedness, we can simply use getRay() to retrieve the ray we want. However, the problem I have is is this doable? Is there a function available to convert a model to its dual form, so then we can explicitly provide the dual to the solver?

In addition, although I've never experienced the infeasibility proved by the barrier algorithm, I'm wondering how I can retrieve the dual extreme ray if it is the case. This post does not provide more details on this.

Thank you so much!

Junhong



------------------------------
Junhong Guo
------------------------------

#DecisionOptimization

Hello,

The information contained in the post you mention is still up to date. As you can see for primal infeasibility getray will work regardless if primal or dual simplex solved the model. Unfortunately for unboundedness things are more complicated. So yes the simplest is probably to implement a try catch in c++.

With barrier without crossover you can't get rays after infeasiblity/unboundedness. This is mainly because those rays may not be very accurate. However, when crossover is used rays can be obtained since in the end primal or dual simplex will be used.

You could use CPXdualwrite to get around this, but in my opinion this is quite a detour. The try catch seems like a better approach. Another workaround could be e.g. to call dual simplex after concurrentopt and then call CPXdualFarkas, but again this seems like a detour.

We actually have it already logged in our internal system that it would be good to provide a single api to get dual rays for concurrentopt on unbounded models. I will make sure to add your feedback.

Thanks,

Christian.

------------------------------
Christian Bliek
------------------------------

Original Message:
Sent: Sat October 10, 2020 08:24 PM
From: Junhong Guo
Subject: Obtain Dual Extreme Ray for Infeasible Primal Using Concurrent Algorithm

Hello,

I'm solving a LP, which I know is infeasible and its dual is unbounded. I just want to get one of the unbounded dual extreme rays.
I'm wondering if there is a neat method to obtain the dual extreme ray (which proves the infeasibility of the primal) when using the concurrent method as the root algorithm.

Since we cannot know upfront whether it is the primal or dual simplex proves the infeasibility, we cannot determine if we should use dualFarkas() or getDuals(). I understand it is workable to use try-catch framework (in C++), but just want to know if there is any other option to deal with this.

A possible way I currently have in my mind is that we explicitly feed the dual formulation of the problem to the solver, and in this case, no matter it is the primal or dual simplex proves the unboundedness, we can simply use getRay() to retrieve the ray we want. However, the problem I have is is this doable? Is there a function available to convert a model to its dual form, so then we can explicitly provide the dual to the solver?

In addition, although I've never experienced the infeasibility proved by the barrier algorithm, I'm wondering how I can retrieve the dual extreme ray if it is the case. This post does not provide more details on this.

Thank you so much!

Junhong



------------------------------
Junhong Guo
------------------------------

#DecisionOptimization