Ripples, complements, and substitutes in generalized networks

The authors extend the qualitative theory of sensitivity analysis for minimum-cost pure network flows of Granot and Veinott to generalized network flow problems, that is, network flow problems where the amount of flow picked up by an arc is multiplied by a (positive) gain while traversing the arc. Three main results are presented. The ripple theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter(s). The theory of substitutes and complements provides necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the value of the parameters to changes in optimal arc flows. Bounds on the rates of changes are also discussed. Compared with pure networks, the presence of gains makes qualitative sensitivity analysis here a much harder task. The authors show the profound effect on computational issues caused by the departure from the pure network structure.