Premium
A composite algorithm for a concave‐cost network flow problem
Author(s) -
Balakrishnan Anantharam,
Graves Stephen C.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190202
Subject(s) - mathematical optimization , minimum cost flow problem , flow network , heuristic , computer science , network planning and design , routing (electronic design automation) , piecewise linear function , arc (geometry) , arc routing , flow (mathematics) , piecewise , flow routing , variety (cybernetics) , algorithm , mathematics , engineering , computer network , mathematical analysis , geometry , artificial intelligence , geotechnical engineering
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 neetworks (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.