Shadow prices for variable bounds in LP

[BC]

Hello,

I was wondering if there is a simple way to retreive shadow prices for
the variable bound constraints, both LB and UB. This does not seem
possible considering the current variable attribute list in the
documentation.

Of course, a way to do this would be to define the variable bounds as
additional constraints in the LP model and then get the dual variables
using the Pi attribute. I am a bit relunctant to do this, however,
because it adds redundant constraints to the model.

Thanks for your help!

[BC]

A quick update - I implemented the variable bounds as additional
constraints. While Gurobi solves the problem, it does not really fix
my problem regarding shadow prices... I suspect denegeracy is the
problem here.

So, I did a little bit more search on shadow prices in degenerate LP
and found an interesting by James K. Ho [INFORMATICA, 2000, Vol. 11,
No. 4, 421–434], that states: <<conventional LP software does not
provide complete shadow prices in general.>> I guess my question is
twofold now:
i. How does Gurobi deal with shadow prices in generate LPs? And in
which situations are the shadow prices 'reliable'?
ii. What procedure could I apply to get reliable shadow price
information? (w/ or /o resolving the LP)

Many thanks! BC

[Greg Glockner]

You can't get the shadow prices from variable bounds. They are not constraints; they are handled internally in the solver. As you noted, you can convert them to constraints; there is modest overhead in the matrix, but this is quickly eliminated by presolve.

[Greg Glockner]

> You can't get the shadow prices from variable bounds. They are not constraints; they are handled internally in the solver. As you noted, you can convert them to constraints; there is modest overhead in the matrix, but this is quickly eliminated by presolve.

Two corrections for the same email. Must be Friday...

First, for variable bounds in an LP, the shadow price equals the reduced cost on the variable. So there's no need to add constraints as I suggested before; just retrieve the reduced cost on the variable.

Now, looking at your second email, it seems that you're looking for economic values rather than reduced costs. You can try to use the barrier algorithm (without crossover), but ultimately you should look at other methods to compute this - subgradients, perturbations, etc.

[Olga Rusyaeva]

I have a question to the author of this post. Now I try to solve the same problem as you mentioned - to find all dual variables and define "true" shadow prices. I wonder if you found a solution to this problem.

Thanks for your help.

пятница, 28 января 2011 г., 11:23:57 UTC+1 пользователь BC написал: