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

Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)231-243
Number of pages13
JournalTransportation Science
Volume23
Issue number4
DOIs
StatePublished - Jan 1 1989

All Science Journal Classification (ASJC) codes

  • Transportation

Fingerprint Dive into the research topics of 'Review of sensitivity results for linear networks and a new approximation to reduce the effects of degeneracy'. Together they form a unique fingerprint.

Cite this