A Sensitivity Analysis of Multicommodity Network Flows

Given the multicommodity flow solution for a current transportation or communication network, planners often require some kind of heuristic measure of the effectiveness of new links which might potentially be added to the network. Exact procedures are usually prohibitive or expensive to use. This paper suggests the use of the dual variables associated with the new arcs. The paper also develops an efficient method for determining these dual variables from the current solution.