Premium
Analysis of a flow problem with fixed charges
Author(s) -
Hochbaum Dorit S.,
Segev Arie
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.3230190304
Subject(s) - heuristics , minimum cost flow problem , flow network , mathematical optimization , multi commodity flow problem , arc (geometry) , computer science , routing (electronic design automation) , flow (mathematics) , fixed cost , lagrange multiplier , variable (mathematics) , maximum flow problem , network planning and design , mathematics , computer network , mathematical analysis , geometry , accounting , business
This article addresses a problem that comes up frequently in network design, and routing. A source is to distribute flows to nodes in the network. Sending flow along an arc involves a fixed cost for using the arc and a variable cost for each ujnit of flow. We show tht the problem of finding a minimum cost collection of arcs along which flows will be directed is an NP‐hard problem. We describe a procedure of solving the problem to optimality and several heuristics. In particular, we conclude that the use of polynomially derived Lagrange multipliers yields good quality solutions and bounds and can be implemented in a distributed processing mode in the network.