Arc tolerances in shortest path and network flow problems

Abstract

Abstract This paper studies one aspect of the “robustness” of optimal solutions to shortest path and, more generally, network flow problems. Specifically, we characterize the maximum increase and the maximum decrease in an arc's cost that can be tolerated without changing optimality of the current solution. Calculation of these quantities is quite simple for nonbasic arcs, and somewhat more involved for basic arcs. When such tolerances are to be determined simultaneously for all arcs in the network, considerable duplication of effort can be avoided through the use of specialized algorithms. Several algorithms for calculating all arc tolerances are presented, one of which is shown to have complexity order n 2 for general networks with n nodes.