## 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.

### MSC:

 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:

### References:

  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  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)  Dantzig, G.B., Linear programming under uncertainity, Management sci., 1, 197-206, (1955) · Zbl 0995.90589  Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103  Fair, G.M.; Geyer, J.C., Water supply and waste-water disposal, (1954), Wiley New York  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  Fillet, A.; Giraud, P.; Sakarovitch, A., An algorithm to find minimum cost flows in networks, ()  Florian, M.; Roberts, P., A direct method to locate negative cycles in a graph, Management sci., 17, 307-310, (1971) · Zbl 0214.18902  Fulkerson, D.R., A network flow computation for project cost curve, Management sci., 7, 167-178, (1961) · Zbl 0995.90519  Fulkerson, D.R., Increasing the capacity of a network—the parametric budget problem, Management sci., 5, 472-483, (1959) · Zbl 0995.90517  Grinold, R.C., Calculating maximal flow in a network with positive gains, Operations res., 21, 528-541, (1973) · Zbl 0304.90043  Hu, T.C., Minimum cost flow in convex cost networks, Naval res. logist. quart., 13, 1-8, (1966)  Hu, T.C., Integer programming and network flows, (1969), Addison-Wesley Reading, MA · Zbl 0197.45701  Kelley, J.R., Critical path planning and scheduling: mathematical basis, Operations res., 9, 296-320, (1961) · Zbl 0098.12103  Klein, M., A primal method for minimum cost flows, Management sci., 14, 205-220, (1976)  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  Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059  McWhite, P.B.; Ratliff, H.D., Modelling mining attrition using networks with gains, ()  Menon, V.V., The minimum cost flow problem with convex costs, Naval res. logist. quart., 12, 163-172, (1965) · Zbl 0209.51101  Minty, G., Monotone networks, (), 194-212 · Zbl 0093.42106  Minty, G., Solving steady state nonlinear networks of monotone elements, Trans. P.G.C.T. (IRE), CT-8, 99-104, (1961)  Murty, K.G., Linear and combinatorial programming, (1976), John Wiley New York · Zbl 0634.90037  Onaga, K., Optimal flows in general communication networks, J. franklin institute, 283, 308-327, (1967) · Zbl 0203.22402  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  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  Truemper, K., On MAX flow with gains and pure MIN-cost flows, SIAM J. appl. math., 32, 450-456, (1977) · Zbl 0352.90069  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.