A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy

Warren B. Powell
Additional contact information
Warren B. Powell: Princeton University, Princeton, New Jersey 08544

Transportation Science, 1989, vol. 23, issue 4, 231-243

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̄ ıj = c ij + (pi) j - (pi) ı . 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.

Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.23.4.231 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:23:y:1989:i:4:p:231-243

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().