# Performance of lp\_rhs\_perturbation\_range

**URL:** <https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551>\
**Category:** Optimization (Mathematical)\
**Created:** [June 1, 2020, 9:48am UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551 "2020-06-01T09:48:02Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![gleyland](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gleyland/32/15339_2.png) [@gleyland](https://discourse.julialang.org/u/gleyland)\
**Post date:** [June 1, 2020, 9:48am UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551/1 "2020-06-01T09:48:02Z")

</div>

Hi,

I have a JuMP model (an LP, currently solved with GLPK) for which I query shadow prices and perturbation ranges of a number of (a few thousand in a large-ish problem) constraints.

Solving the LP takes a couple of seconds. Obtaining margin information takes hundreds. Does it have to take this long, and there anything that can be done about it?

I’ve had a quick dig with the profiler, and it seems like lp\_rhs\_perturbation\_range is the main culprit. As far as I can tell, every call to lp\_rhs\_perturbation\_range spends a lot of its time in \_std\_matrix and \_std\_basis\_status, and, it would seem that given that the only arguments to these functions are the Model, that on each call, they’re generating the same matrix and basis status.

If this is correct, would it be feasible to either call lp\_rhs\_perturbation\_range with a vector of right-hand sides, or, perhaps to cache the results of \_std\_matrix and \_std\_basis status somewhere in the model?

Thanks in advance!  
Geoff

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [June 1, 2020, 2:17pm UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551/2 "2020-06-01T14:17:00Z")

</div>

Geoff,

Yes, it looks like code is pretty slow. I’ve opened an issue:

> <https://github.com/jump-dev/JuMP.jl/issues/2244>
>
> As raised on Discourse: https://discourse.julialang.org/t/performance-of-lp-rhs-…perturbation-range/40551
> 
> The function for querying LP sensitivity are pretty slow, mainly because they compute the constraint matrix every call:
> https://github.com/JuliaOpt/JuMP.jl/blob/7df1796d305aed88ec4f66ea52b8437fa4babe58/src/lp\_sensitivity.jl#L190-L192
> 
> There is probably plenty of other low-hanging fruit we could improve.
> 
> Edit: in fact, it seems the best thing we could do is compute and return a dictionary with the perturbation range for every constraint.

What are you using the perturbation ranges for?

---

<div class="post-metadata">

**Author:** ![gleyland](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gleyland/32/15339_2.png) [@gleyland](https://discourse.julialang.org/u/gleyland)\
**Post date:** [June 1, 2020, 8:57pm UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551/3 "2020-06-01T20:57:35Z")

</div>

Thanks Oscar!

We use the shadow prices and perturbation ranges to give users messages like: “If you did some more of X, then you would get more of Y, up to N units of X”. If they’re well guided, users can do a surprising amount to relieve constraints.

The ranges are a nicety in the messages, so I can save time by leaving them out, or, if possible, provide them on demand later (for which I have a question about copying Models, but I’ll ask that in a separate thread).

Cheers,  
Geoff

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [June 1, 2020, 9:10pm UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551/4 "2020-06-01T21:10:40Z")

</div>

Interesting. We were envisaging that this would only be used for small pedagogical examples, so performance wasn’t a high priority. But this use case makes a lot of sense. How important is the “up to N units of X”? Can’t you just tell them the dual?

I don’t have time to look this week (it’s the last week of the quarter), but I may have time towards the end of next week. Alternately, it probably isn’t too much work if you can spare John or someone for the engineering time. I think the way to go is just to compute the ranges once for all constraints and return a dictionary mapping constraint indices to the range, rather than doing it one-by-one for each constraint.

---

<div class="post-metadata">

**Author:** ![gleyland](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gleyland/32/15339_2.png) [@gleyland](https://discourse.julialang.org/u/gleyland)\
**Post date:** [June 1, 2020, 10:01pm UTC](https://discourse.julialang.org/t/performance-of-lp-rhs-perturbation-range/40551/5 "2020-06-01T22:01:13Z")

</div>

You’re exactly right, the range is a “nice-to-have”, rather than essential, and I’ll experiment with providing margins on demand, rather than my current, rather crude “solve the model, and find all the margins at once and keep the user waiting” process.

That said, the ranges

- give us some confidence that the margins are worthwhile, since apparent “high-value” margins stop quite suddenly at a nearby constraint
- give users an estimate of what kind of change to try, if the are able to make a change.

The domain is dairy processing, and we have regional models, so the margins could, for example say “if you move more cream from region A to region B, you could…”. So it’s helpful to know both the value of moving the cream, and a rough estimate of quantity that might be worth moving.