A parametric algorithm for convex cost network flow and related problems. (English) Zbl 0532.90034

Summary: The context cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem The optimum basis structure is then used to parametrize v, the flow to be transshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.


90B10 Deterministic network models in operations research
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Bansal, P.P.; Jacobson, S.E., An algorithm for optimizing network flow capacity under economies of scale, J. optimization theory appl., 15, 565-586, (1975) · Zbl 0281.90077
[2] Beale, E.M.L., An algorithm for solving the transportation problem when the shipping cost over each route is convex, Naval res. logist. quart., 6, 43-56, (1959)
[3] Dantzig, G.B., Linear programming under uncertainity, Management sci., 1, 197-206, (1955) · Zbl 0995.90589
[4] Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103
[5] Fair, G.M.; Geyer, J.C., Water supply and waste-water disposal, (1954), Wiley New York
[6] Ferguson, A.R.; Dantzig, G.B., The allocation of aircraft to routes—an example of linear programming under uncertain demand, Management sci., 3, 45-73, (1956) · Zbl 0995.90522
[7] Fillet, A.; Giraud, P.; Sakarovitch, A., An algorithm to find minimum cost flows in networks, ()
[8] Florian, M.; Roberts, P., A direct method to locate negative cycles in a graph, Management sci., 17, 307-310, (1971) · Zbl 0214.18902
[9] Fulkerson, D.R., A network flow computation for project cost curve, Management sci., 7, 167-178, (1961) · Zbl 0995.90519
[10] Fulkerson, D.R., Increasing the capacity of a network—the parametric budget problem, Management sci., 5, 472-483, (1959) · Zbl 0995.90517
[11] Grinold, R.C., Calculating maximal flow in a network with positive gains, Operations res., 21, 528-541, (1973) · Zbl 0304.90043
[12] Hu, T.C., Minimum cost flow in convex cost networks, Naval res. logist. quart., 13, 1-8, (1966)
[13] Hu, T.C., Integer programming and network flows, (1969), Addison-Wesley Reading, MA · Zbl 0197.45701
[14] Kelley, J.R., Critical path planning and scheduling: mathematical basis, Operations res., 9, 296-320, (1961) · Zbl 0098.12103
[15] Klein, M., A primal method for minimum cost flows, Management sci., 14, 205-220, (1976)
[16] Klingman, D.; Napier, A.; Stutz, J., NETGEN—A program for generating large scale (uncapacitated assignment, transportation, and minimum cost flow network problems, Management sci., 20, 814-821, (1974) · Zbl 0303.90042
[17] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059
[18] McWhite, P.B.; Ratliff, H.D., Modelling mining attrition using networks with gains, ()
[19] Menon, V.V., The minimum cost flow problem with convex costs, Naval res. logist. quart., 12, 163-172, (1965) · Zbl 0209.51101
[20] Minty, G., Monotone networks, (), 194-212 · Zbl 0093.42106
[21] Minty, G., Solving steady state nonlinear networks of monotone elements, Trans. P.G.C.T. (IRE), CT-8, 99-104, (1961)
[22] Murty, K.G., Linear and combinatorial programming, (1976), John Wiley New York · Zbl 0634.90037
[23] Onaga, K., Optimal flows in general communication networks, J. franklin institute, 283, 308-327, (1967) · Zbl 0203.22402
[24] Phillips, S.; Dessouki, M.I., Solving the project time-cost tradeoff problems using the minimal cut concept, Management sci., 24, 393-400, (1977) · Zbl 0371.90039
[25] Price, W.L., Increasing the capacity of a network where the costs are nonlinear: A branch and bound approach, Cors j., 5, 110-114, (1967) · Zbl 0166.15704
[26] Truemper, K., On MAX flow with gains and pure MIN-cost flows, SIAM J. appl. math., 32, 450-456, (1977) · Zbl 0352.90069
[27] Weintraub, A.F., A primal algorithm to solve network flow problem with convex costs, Management sci., 21, 87-97, (1974) · Zbl 0319.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.