Computing the Minimum Cost Pipe Network Interconnecting One Sink and Many Sources
Authors:
- Guoliang XueGXGuoliang Xue
- Theodore P. LillysTLTheodore P. Lillys
- David E. DoughertyDDDavid E. Dougherty
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 10 (1) , 22-42
Abstract
In this paper, we study the problem of computing the minimum cost pipe network interconnecting a given set of wells and a treatment site, where each well has a given capacity and the treatment site has a capacity that is no less than the sum of all the capacities of the wells. This is a generalized Steiner minimum tree problem which has applications in communication networks and in groundwater treatment. We prove that there exists a minimum cost pipe network that is the minimum cost network under a full Steiner topology. For each given full Steiner topology, we can compute all the edge weights in linear time. A powerful interior-point algorithm is then used to find the minimum cost network under this given topology. We also prove a lower bound theorem which enables pruning in a backtrack method that partially enumerates the full Steiner topologies in search for a minimum cost pipe network. A heuristic ordering algorithm is proposed to enhance the performance of the backtrack algorithm. We then define the notion of k-optimality and present an efficient (polynomial time) algorithm for checking 5-optimality. We present a 5-optimal heuristic algorithm for computing good solutions when the problem size is too large for the exact algorithm. Computational results are presented.Keywords
This publication has 23 references indexed in Scilit:
- Two Heuristics for the Euclidean Steiner Tree ProblemJournal of Global Optimization, 1998
- An Efficient Newton Barrier Method for Minimizing a Sum of Euclidean NormsSIAM Journal on Optimization, 1996
- Improved computation of plane Steiner Minimal TreesAlgorithmica, 1992
- A projected newton method forl p norm location problemsMathematical Programming, 1987
- Exact computation of Steiner minimal trees in the planeInformation Processing Letters, 1986
- A Stable Algorithm for Solving the Multifacility Location Problem Involving Euclidean DistancesSIAM Journal on Scientific and Statistical Computing, 1980
- Optimal diameter assignment for gas pipeline networksThe Journal of the Australian Mathematical Society. Series B. Applied Mathematics, 1979
- The Complexity of Computing Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1977
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- Minimum cost communication networksBell System Technical Journal, 1967