Extreme ray values unbounded LP JuMP

Specific Domains Optimization (Mathematical)
, ,
1

I’m currently dealing with an LP problem where the solution to the primal turns out to be infeasible, leading to an unbounded dual. In order to create a feasibility cut, I’m aiming to acquire the extreme ray values from the unbounded dual. I’ve explored options like JuMP.dual() and JuMP.shadow_price(), but these functions don’t seem to provide dual extreme ray values.

Could someone enlighten me if there’s a function in JuMP that can facilitate this process? My intention is to solve the primal and extract the extreme ray values directly, without having to manually implement the dual formulation.

2

I’m not sure about the extreme rays, but you can create the dual with GitHub - jump-dev/Dualization.jl: Automatic dualization feature for MathOptInterface.jl

3

Yes thank you, I also came across that package but was wondering if JuMP had build in functionality for that because you can get extreme rays directly from Gurobi https://www.gurobi.com/documentation/9.1/refman/unbdray.html

4

Do you have a reproducible example?

If dual_status(model) is INFEASIBILITY_CERTIFICATE, then the dual(constraint) is the associated dual ray.

In some cases, even if the problem is unbounded, the solver might not return a dual ray. In this case, the dual status is NO_SOLUTION. You might need to set some solver options, like disabling presolve, in order to force the solver to compute a certificate.

See also Stuck with infeasibility certificates in JuMP.jl

5

Ah. I’m guessing this is the same question as Benders Subproblem Infeasibility - #2 by odow? If so, let’s just keep to the other thread. No need to duplicate things :slight_smile: (I was sick yesterday, so sorry for the delayed reply. I do see and reply to all the JuMP questions here.)

1 Like
6

Indeed, I tried simplifying the question here. Thanks for the help, I responded in the other Thread.

1 Like