Abstract
The problem of optimally allocating a fixed budget to the various arcs of a single-source, single-sink network for the purpose of maximizing network flow capacity is considered. The initial vector of arc capacities is given, and the cost function, associated with each arc, for incrementing capacity is concave; therefore, the feasible region is nonconvex. The problem is approached by Benders' decomposition procedure, and a finite algorithm is developed for solving the nonconvex relaxed master problems. A numerical example of optimizing network flow capacity, under economies of scale, is included.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Fulkerson, D. R.,Increasing the Capacity of a Network, Management Science, Vol. 5, pp. 472–483, 1959.
Beale, E. M. L., andTomlin, J. A.,Special Facilities in a Generalized Mathematical Programming System for Nonconvex Problems Using Ordered Sets of Variables, 5th International Conference on Operations Research, Edited by J. Lawrence, Tavistock Publications, London, England, 1969.
Tomlin, J. A.,Branch and Bound Methods for Integer and Non-Convex Programming, Integer and Nonlinear Programming, Edited by J. Abadie, North-Holland Publishing Company, Amsterdam, Holland, 1970.
Price, W. L.,Increasing the Capacity of a Network Where the Costs Are Non-Linear: A Branch-and-Bound Algorithm, CORS Journal, Vol. 5, pp. 110–114, 1967.
Yaged, B., Jr.,Minimum Cost Routing for Static Network Models, Networks, Vol. 1, pp. 139–172, 1971.
Soland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, II, Nonconvex Constraints, Management Science, Vol. 17, pp. 759–773, 1971.
Rosen, J. B.,Iterative Solution of Nonlinear Optimal Control Problems, SIAM Journal on Control, Vol. 4, pp. 223–244, 1966.
Meyer, R.,The Validity of a Family of Optimization Methods, SIAM Journal on Control, Vol. 8, pp. 41–54, 1970.
Benders, J. F.,Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numeriche Mathematik, Vol. 4, pp. 238–252, 1962.
Geoffrion, A. M.,Generalized Benders Decomposition, Journal of Optimization Theory and Applications, Vol. 4, pp. 237–260, 1972.
Bansal, P. P., andJacobsen, S. E.,Characterization of Local Solutions for a Class of Nonconvex Programs, Journal of Optimization Theory and Applications, Vol. 15, No. 5, 1975.
Falk, J. E., andSoland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, Management Science, Vol. 15, pp. 550–569, 1969.
Author information
Authors and Affiliations
Additional information
Communicated by C. T. Leondes
This research was supported by the National Science Foundation, Grant No. GK-32791.
Rights and permissions
About this article
Cite this article
Bansai, P.P., Jacobsen, S.E. An algorithm for optimizing network flow capacity under economies of scale. J Optim Theory Appl 15, 565–586 (1975). https://doi.org/10.1007/BF00933746
Issue Date:
DOI: https://doi.org/10.1007/BF00933746