A Polynomially Bounded Algorithm for a Nonlinear Network Allocation Problem

This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks.

• 저널Management Science · 27(9) · 1054–1066
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.27.9.1054
• 저자T. R. Elken, H. T. Freedman, A. E. Gibson