RIPPLES, COMPLEMENTS, AND SUBSTITUTES IN SINGLY CONSTRAINED MONOTROPIC PARAMETRIC NETWORK FLOW PROBLEMS

We extend the qualitative theory of sensitivity analysis for minimum-c ost flow problems developed by Granot and Veinott to minimum-cost flow problems with one additional linear constraint. Two natural extension s of the ''less dependent on'' partial ordering of the arcs are presen ted. One is decidable in linear time, whereas the other yields more in formation but is NP-complete in general. The Ripple Theorem gives uppe r bounds on the absolute value of optimal-flow variations as a functio n of variations in the problem parameters. The theory of substitutes a nd complements presents necessary and sufficient conditions for optima l-flow changes to consistently have the same (or the opposite) sign in two given arcs. The Monotonicity Theory links the changes in the valu e of the parameters to the change in the optimal arc-flows, and bounds on the rates of changes are discussed. The departure from the pure ne twork structure is shown to have a profound effect on computational is sues. Indeed, the complexity of determining substitutes and complement s, although linear for the unconstrained (no additional constraint) ca se, is shown to be NP-complete in general for the constrained case. Ho wever, for all intractable problems, families of cases arise from easi ly recognizable graph structures which can be computed in linear time. (C) 1994 John Wiley & Sons, Inc.