Qualitative sensitivity analysis in monotropic programming

Optimal selections are parameter-dependent optimal solutions of parametric optimization problems whose properties can be used in sensitivity analysis. Here we present a qualitative theory of sensitivity analysis for linearly- constrained convex separable (i.e., monotropic) parametric optimization pro blems. Three qualitative sensitivity analysis results previously derived fo r network flows are extended to monotropic problems: The Ripple and Smoothi ng Theorems give upper bounds on the magnitude of optimal-variable variatio ns as a function of variations in the problem parameter(s), the theory of s ubstitutes and complements provides necessary and sufficient conditions for optimal-variable changes to consistently have the same (or the opposite) s ign(s) in two given variables, and the Monotonicity Theorem links changes i n the value of the parameters to changes in optimal decision variables. We introduce a class of optimal selections for which these results hold, there by answering a long-standing question due to Granot and Veinott (1985) with a simple and elegant method. Although a number of results are known to dep end on the resolution of NP-complete problems, easily computable nonnetwork classes of monotropic problems such as unimodular systems of constraints e merge in the light of the present approach.