Derive "true" shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)

Question

In linear programming for an optimal primal degenerate solution the values of the dual variables are in general not identical with the corresponding shadow prices. Several proposals on how to find the "true" shadow prices have been made and terms like "two-sided-shadow prices" (one for decrease of the capacity of the relevant constraint and one for increase) have been coined (Gal 1986).

The case of an optimal basic solution which is primal degenerated occurs frequently in practice (Pan 1998).

Not the question is how can I get the "true" shadow prices?

All approaches that I have found so far require modification of the LP and therefore some kind of resolving. To me this does not seem feasible for large real world problems.

This leads to three questions:

1. Why is this not a larger problem in the industry or why do commercial solver not address this by providing the functionality to determine the "true" shadow prices in case of degeneracy (even if it is a performance trade off)?

2. What steps can I take to still use shadow prices? One Option is the reduction/exclusion of redundant constraints but I am not sure if this is always possible in larger problems.

3. Degeneracy does not falsify all shadow prices (at least that is my experience so far). Is there a way to determine which shadow prices are falsified due to degeneracy and which aren't? Maybe by identifying the responsible basic variables (the ones that take 0 value)?

Answer 1

I find the phrase "true shadow prices" misleading, and the use of "falsified" even more so, since the shadow prices any reputable solver returns are valid shadow prices ... possibly only in one direction, or even for a zero step size in either direction, when degeneracy occurs, but still correct.

1. I can't say why it's "not a larger problem in the industry", but as to why solvers do not provide mechanisms to reveal all shadow prices, I suspect it is because the results would be hard to present in an interpretable manner. If degeneracy only affects one shadow price, that's easy, but when a basic feasible solution involves multiple sources of degeneracy, you get into a combinatorial mess ("if you increase this RHS and that RHS but decrease this other RHS, then these are the relevant shadow prices").

2. You can answer specific questions along the lines of "what is the marginal impact of increasing this RHS?" by combining shadow prices with sensitivity results, which every solver I've used provide. The sensitivity output tells you how much you can increase (or decrease) any RHS in isolation without making the current basic solution infeasible or suboptimal (forcing a pivot). If you are changing one RHS, as long as you stay in this range, the shadow price is valid. If you need to know what the shadow price is outside the range, you have to perturb the constraint and update the solution. (Fortunately, with dual simplex this is usually not horribly expensive.) If you are changing multiple constraints, there is a slightly conservative result you can use: express each change as a fraction of the allowable change in that direction according to the sensitivity info, and if the fractions sum to at most 1, all the shadow prices will be valid over that change.

3. If the sensitivity information for a constraint has nonzero change limits in both directions, the shadow price is valid for small perturbations in either direction. If it allows a nonzero change in one direction but a zero change in the other, the shadow price is valid in the first direction but may be invalid in the second one. If both change limits are zero, don't trust the shadow price for anything.