A composite algorithm for a concave-cost network flow problem. (English) Zbl 0673.90034

Summary: We consider the problem of routing multiple commodities between various origin-destination pairs in a network, at minimum total cost. Economies of scale in arc flow costs are modeled using piecewise linear, concave total-cost functions for each arc. This model applies to a variety of medium- and long-term planning contexts including transportation planning, design of communication networks, plant location and capacity expansion planning, production planning, and water resource management. We formulate the general problem as a mixed-integer program and develop a composite algorithm to generate both good lower bounds and heuristic solutions. We also report on computational results for several randomly generated general networks (with up to 40 nodes, 359 arcs, and 60 commodities) and layered networks (with up to 60 nodes, 372 arcs, and 60 commodities). These tests demonstrate that even for relatively large problems, the composite algorithm is very effective in generating solutions with small gaps between the upper and lower bounds (1.7% on average for general networks, and 0.4% on average for layered networks); for 19 out of the 25 layered network problems, the method generated and verified the optimal solution.


90B10 Deterministic network models in operations research
90C11 Mixed integer programming
65K05 Numerical mathematical programming methods
90B05 Inventory, storage, reservoirs
90C90 Applications of mathematical programming
90B30 Production models
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Valid Inequalities and Algorithms for the Network Design Problem with an Application to LTL Consolidation. Doctoral dissertation, Sloan School Management, Massachusetts Institute of Technology, Cambridge, MA (1984).
[2] Crowder, Symp. Math. 19 pp 357– (1976)
[3] Dijkstra, Numerische Math. 1 pp 269– (1959)
[4] Erickson, Math. Oper. Res. 12 pp 634– (1987)
[5] Fisher, Management Sci. 27 pp 1– (1981)
[6] Gallo, Eur. J. Oper. Res. 3 pp 239– (1979)
[7] Geofffion, Math. Programming Study 2 pp 82– (1974)
[8] Johnson, Netwoprks 8 pp 279– (1978)
[9] Less-Than-Truckload freight consolidation and routing strategies: A mathematical programming procedure. Project report no. CTS/IU-83.2, Center for Transportation Studies, Massachusetts Institute of Technology, Cambridge, MA (1983).
[10] , and , Bounding procedures for fixed charge, multicommodity network design problems. Working paper, Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MA (1984).
[11] Magnanti, Trans. Sci. 18 pp 1– (1984)
[12] A local improvement heuristic for the design of less-than-truckload motor carrier networks. Working paper EES-85-3, Princeton University, Princeton, NJ (1985).
[13] Powell, Trans. Res. 17A pp 471– (1983)
[14] Soland, Oper. Res. 22 pp 373– (1974)
[15] Zangwill, Management Sci. 14 pp 429– (1968)
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.