Asymptotic Approximations for the Transportation LP and Other Scalable Network Problems

Network optimization problems with a "scalable" structure are examined in this report. Scalable networks are embedded in a normed space and must belong to a closed family under certain transformations of size (number of nodes) and scale (dimension of the norm). The transportation problem of linear programming (TLP) with randomly distributed points and random demands, the earthwork minimization problem of highway design, and the distribution of currents in an electric grid are examples of scalable network problems. Asymptotic formulas for the optimum cost are developed for the case where one holds the scale parameter constant while increasing the size parameter, N. As occurs in some applied probability problems such as the Ising model of statistical mechanics, and the first passage of time of a random walk, the nature of the solution of linear problems depends on the dimensionality of the space. In the linear case, we find that the cost per node is bounded from above in 3+ dimensions (3+-D), but not in 1- and 2-D. Curiously, zone shape has no effect (asymptotically) on the optimum cost per point in 2+-D, but it has an effect in 1-D. Therefore, the 2-D case can be viewed as a transition case that shares some of the properties of 1-D (unbounded cost) and some of the properties of 3-D (shape-independence). A simple formula for the 2-D, Euclidean TLP is given. Asymptotic results are also developed for a class of non-linear network problems with link costs that are a concave power function of flow. It is found that if these functions are strictly concave than the solution in 2+-D is bounded.