Least d-Majorized Network Flows with Inventory and Statistical Applications

It is shown that for any feasible network flow model, there is a flow which simultaneously minimizes every d-Schur convex function of the flows emanating from a single distinguished node called the source. The vector of flows emanating from the source in the minimizing flow is unique and is the "least d-majorized" flow. This flow can be found by solving the problem for the special case where the d-Sehur convex function is separable and quadratic. Once this flow is found, the solution of the dual problem is reduced to evaluating the conjugate of a function appearing in the dual objective function at the above flow. This computation is extremely simple when the function is separable. These results are extended to situations in which the variables must be integers. An important special case of the problem can be solved geometrically by choosing, from among all paths joining two points in the plane and lying between two given nonintersecting paths, the path with minimum euclidian length. Applications of the results are given, to deterministic production-distribution models (e.g., the Modigliani-Hohn [30] production smoothing model), certain of the stochastic inventory-redistribution models examined by Ignall and Veinott [27], a deterministic price speculation and storage model (including Cahn's warehouse problem [11]), and a zero lead time case of the Clark-Scarf series multi-echelon model [13]. In addition, applications are given to several maximum likelihood estimation problems in which the parameters satisfy certain linear inequalities, e.g., those surveyed in Brunk [8], [9, pp. 1347-1349], and a few others.