TY - JOUR

T1 - Review of sensitivity results for linear networks and a new approximation to reduce the effects of degeneracy

AU - Powell, Warren Buckler

PY - 1989/1/1

Y1 - 1989/1/1

N2 - Estimating the reduced cost of an upper bound in a classical linear transshipment network is traditionally accomplished using the shadow price for this constraint, given by the standard calculation c̄ij = cij + πj - πi. This reduced cost is only a subgradient due to network degeneracy and often exhibits errors of 50% or more compared to the actual change in the objective function if the upper bound were raised by one unit and the network reoptimized. A new approximation is developed, using a simple modification of the original reduced cost calculation, which is shown to be significantly more accurate. This paper summarizes the basic theory behind network sensitivity, much of which is known as folklore in the networks community, to establish the theoretical properties of the new approximation. The essential idea is to use least-cost flow augmenting paths in the basis to estimate certain directional derivatives which are used in the development of the approximation. The technique is motivated with an application to pricing in truckload trucking.

AB - Estimating the reduced cost of an upper bound in a classical linear transshipment network is traditionally accomplished using the shadow price for this constraint, given by the standard calculation c̄ij = cij + πj - πi. This reduced cost is only a subgradient due to network degeneracy and often exhibits errors of 50% or more compared to the actual change in the objective function if the upper bound were raised by one unit and the network reoptimized. A new approximation is developed, using a simple modification of the original reduced cost calculation, which is shown to be significantly more accurate. This paper summarizes the basic theory behind network sensitivity, much of which is known as folklore in the networks community, to establish the theoretical properties of the new approximation. The essential idea is to use least-cost flow augmenting paths in the basis to estimate certain directional derivatives which are used in the development of the approximation. The technique is motivated with an application to pricing in truckload trucking.

UR - http://www.scopus.com/inward/record.url?scp=0024769872&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024769872&partnerID=8YFLogxK

U2 - 10.1287/trsc.23.4.231

DO - 10.1287/trsc.23.4.231

M3 - Article

AN - SCOPUS:0024769872

VL - 23

SP - 231

EP - 243

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 4

ER -