Singly-constrained monotropic network flow problems : a linear time transformation to unconstrained problems and qualitative sensitivity analysis

This thesis examines several problems related to singly-constrained Monotropic Network Flow Problems. In the first part, a linear time algorithm that reduces the solution of a monotropic network flow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singly-constrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a linear-time transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given. In the second part the qualitative theory of sensitivity analysis for Unconstrained Minimum-Cost Flow Problems presented by Granot and Veinott [GV85] is extended to Minimum-Cost Flow Problems with one additional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natural extensions of the "less-dependent-on" partial ordering of the arcs given in [GV85] are presented. One is decidable in linear time while the other yields more information but is NP-complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter. Moreover, it shows how changes may "ripple down" throughout the network, decreasing in magnitude as one gets "further away" from the arc whose parameter initiated the change. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign in two given arcs. The complexity of determining Substitutes and Complements is shown to be NP-complete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in linear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc-flows. Bounds on the rates of changes are discussed. We further provide a number of practical situations where our theory may apply. We discuss some Multi-Period Multi-Product Inventory-Production models that can be formulated as nonlinear parametric network flow problems with one additional linear constraint. We then apply our theory to help decision makers understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inventory carrying costs without additional computation. In a second example, we show how a Cash-Flow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. The theory is then recommended as a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation.Business, Sauder School ofGraduat