On Network Flow Problems with Convex Cost

Authors

  • V. A. Nguyen School of Electrical & Electronic Engineering Nanyang Technological University, Singapore
  • Y. P. Tan School of Electrical & Electronic Engineering Nanyang Technological University, Singapore

DOI:

https://doi.org/10.32890/jict2004.3.1.3

Keywords:

Minimum cost flow problem, convex cost functions, primal-dual, algorithm, network flow

Abstract

Minimum cost flow (MCF) problem is a typical example of network flow problems, for which an additional constraint of cost is added to each flow. Conventional MCF problems consider the cost constraints as linear functions of flow. In this paper, we extend the MCF problem to cover cost functions as strictly convex and differentiable, and refer to the problem as convex cost flow problem. To address this problem, we derive the optimality conditions for minimising convex and differentiable cost functions, and devise an algorithm based on the primal-dual algorithm commonly used in linear programming. The proposed algorithm minimises the total cost of flow by incrementing the network flow along augmenting paths of minimum cost. Simulation results are provided to demonstrate the efficacy of the proposed algorithm.

 

References

Aashtiani, H. A., & Magnanti, T. L. (1976). Implementing primal-dual network flow algorithms. Working Paper OR 055-76, Operations Research Center, Massachusetts Inst. of Technology, Cambridge, Mass.

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows. Theory, algorithms, and applications. Englewood Cliffs, N.J.: Prentice Hall. — Bertsekas, D., & Gallager, R. (1992). Data networks. Prentice-Hall.

Busacker, R. G., & Gowen, P. J. (1961). A procedure for determining a family of minimum-cost network, flow patterns. "Technical Report 15, Operations Research Office, John Hopkins University.

Dantzig, G. B. (1963). Linear programming and extensions. New Jersey: Princeton University Press.

Ford, L. R., & Fulkerson, D. R. (1956). Maximum flow through a network. Canadian Journal of Mathematics, 8, 399-404.

Fulkerson, D. R. (1961). An out-of-kilter method for minimal cost flow problems. SLAM Journal, 9,13-27. BS E //jict.uum.ed http Journal of ICT, 3 (1), pp: 33-

Goldberg, A. V., & Tarjan, R. E. (1988). Finding minimum-cost circulations by canceling negative cycles. Journal of ACM, 36, 873-886.

Goldfarb, D., & Lin, Y. (2002). Combinatorial interior point methods for generalized network flow problem. Mathematical Programming, Serial A 93, 227-246.

Jewell, W. S. (1958). Optimal flow through networks. Technical Report 8, Operations Research Center, MIT.

Kamesam, P. V., & Meyer, R. R. (1984). Multipoint methods for separable nonlinear networks. Mathematical Programming Study, 22, 185-205.

Kapoor, S., & Vaidya, P. M. (1986). Fast algorithms for convex quadratic programming and multi-commodity flows. 18th Annual ACM Symposium on Theory of Computing, 147-159.

Karzanov, A. V., & McCormick, S. T. (1997). Polynomial methods for separable convex optimization in unmodular linear spaces with applications. SLAM Journal on Computing, 4, 1245-1275.

Kennington, J. L., & Wang, Z. (1991). An empirical analysis of the dense assignment problem: Sequential and parallel implementations. ORSA. J. Computing, 3, 299-306.

Klein, M. (1967). A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science, 14, 205-220.

Klein, P., Plotkin, S., Stein, C., & Tardos, E. (1994). Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SL4M Journal on Computing, 23(2), 466-487.

Leighton, T., & Rao, S. (1988). An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms. 29th IEEE Annual Symposium on Foundations of Computer Science, 422-431. Journal of ICT, 3 (1), pp: 33-

Meyer, R. R. (1979). Two-segment separable programming. Management Science, 25, 285-295.

Trustrum, K. (1971). Linear programming. London: Routledge and Kegan Paul Ltd.

Vygen, J. (2002). On dual minimum cost flow algorithms. Mathematical methods of operations research, 56, 101-126.

DN Wallacher, C., & Zimmermann, U. (1992). A combinatorial interior point method for network flow problems. Mathematical Programming, 56, 321-335. mM - Wayne, K. D. (2002). A polynomial combinatorial algorithm for generalized minimum cost flow. Mathematics of Operations Research, 27(3), 445-459. //ict.uum.ed http

Downloads

Published

25-05-2004

Issue

Vol. 3 No. 1 (2004): Journal of Information and Communication Technology (JICT) Vol. 3, No.1 June 2004

Section

Articles

How to Cite

Nguyen, V. A., & Tan, Y. P. (2004). On Network Flow Problems with Convex Cost. Journal of Information and Communication Technology, 3(1), 33-51. https://doi.org/10.32890/jict2004.3.1.3

Research impact

Harvested 2026-09-06
2 citations, from OpenAlex — the highest of the sources checked

Counts differ between services because each indexes a different body of literature. None of them is the whole picture.

Identifiers DOI 10.32890/jict2004.3.1.3 OpenAlex W1535814080