Abstract
A relaxation method for separable convex network flow problems is developed that is well-suited for problems with large variations in the magnitude of the nonlinear cost terms. The arcs are partitioned into two sets, one of which contains only arcs corresponding to strictly convex costs. The algorithm adjusts flows on the other arcs whenever possible, and terminates with primal-dual pairs that satisfy complementary slackness on the strictly convex arc set and ∈-complementary slackness on the remaining arcs. An asynchronous parallel variant of the method is also developed. Computational results demonstrate that the method is significantly more efficient on ill-conditioned networks than existing methods, solving problems with several thousand nonlinear arcs in one second or less.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Bertsekas, Linear Network Optimization: Algorithms and Codes, The MIT Press: Cambridge, MA, 1991.
D.P. Bertsekas, P.A. Hosein, and P. Tseng, “Relaxation methods for network flow problems with convex arc costs,” SIAM Journal on Control and Optimization, vol. 25, pp. 1219–1243, 1987.
D. Bertsekas, L. Polymenakos, and P. Tseng, “An ε-relaxation method for separable convex cost network flow problems,” SIAM Journal on Optimization, vol. 7, pp. 953–970, 1997.
D. Bertsekas and J. Tsitsiklis, Parallel and Distributed Computation, Prentice Hall: Englewood Cliffs, NJ, 1989.
M. Collins, L. Cooper, R. Helgason, J. Kennington, and L. LeBlanc, “Solving the pipe network analysis problem using optimization techniques,” Management Science, vol. 24, pp. 747–760, 1978.
T. Hu, “Minimum cost flows in convex cost networks,” Naval Research Logistics Quarterly, vol. 13, pp. 1–9, 1966.
P. Kamesam and R. Meyer, “Multipoint methods for separable nonlinear networks,” Mathematical Programming Study, vol. 22, pp. 185–205, 1984.
D. Klingman, A. Napier, and J. Stutz, “NETGEN—A program for generation of large-scale (un)capacitated assignment, transportation and minimum cost network problems,” Management Science, vol. 20, pp. 814–822, 1974.
T. Magnanti, “Models and algorithms for predicting urban traffic equilibria,” in Transportation Planning Models, M. Florian (Ed.), North-Holland: Amsterdam, 1984, pp. 153–186.
C. Monma and M. Segal, “A primal algorithm for finding minimum-cost flows in capacitated networks with applications,” Bell System Technical Journal, vol. 61, pp. 449–468, 1982.
R. Rockafellar, Convex Analysis, Princeton University Press: Princeton, NJ, 1970.
R. Rockafellar, Network Flows and Monotropic Optimization, John Wiley: New York, 1984.
P. Toint and D. Tuyttens, “LSNNO: A Fortran subroutine for solving large-scale nonlinear network optimization problems,” ACM Transactions on Mathematical Software, vol. 18, pp. 308–328, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
De Leone, R., Meyer, R.R. & Zakarian, A. A Partitioned ∈-Relaxation Algorithm for Separable Convex Network Flow Problems. Computational Optimization and Applications 12, 107–126 (1999). https://doi.org/10.1023/A:1008667714641
Issue Date:
DOI: https://doi.org/10.1023/A:1008667714641