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

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.

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)?

• In the context of linear programming, degeneracy (at least the value of one of the basic variables is equal to zero) is accrued when in the pivot operation at least two elements have the same value and it is not unique, while shadow price is related to the changing in the RHS of the constraint and its behaviour on the objective function value. Would you say please, what you mean by "which shadow price is falsified due to degeneracy"? Oct 14, 2020 at 15:20
• Thanks for the clarifying question! Let's suppose we have a non-degenerate optimal solution and introduce an additional constraint which leads to degeneracy. I can identify the basic variable which is equal zero or the binding constraints with allowable increase/decrease 0 but can I deduce that only the shadow price for those constraints is "falsified" or rather isn't equivalent to the improvement of my objective function if I have one more unit of the corresponding resource? Maybe there is some other connection like: each constraint containing the basic variable (=0) is "falsified" Oct 14, 2020 at 16:23