4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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"? $\endgroup$
    – A.Omidi
    Oct 14, 2020 at 15:20
  • $\begingroup$ 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" $\endgroup$
    – Mitch
    Oct 14, 2020 at 16:23

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.