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.
Computing the Minimum Cost Pipe Network Interconnecting One Sink and Many Sources
Xue, G., Lillys, T. P., & Dougherty, D. (1999). Computing the Minimum Cost Pipe Network Interconnecting One Sink and Many Sources. SIAM Journal on Optimization, 10(1), 22-42. https://doi.org/10.1137/S1052623496313684
Abstract
Publications Info
To contact an RTI author, request a report, or for additional information about publications by our experts, send us your request.
Meet the Experts
View All ExpertsRecent Publications
Article
Treatment preferences among patients with mild-to-moderate atopic dermatitis
Article
Multifaceted risk for non-suicidal self-injury only versus suicide attempt in a population-based cohort of adults
Article
Spatiotemporal analysis exploring the effect of law enforcement drug market disruptions on overdose, Indianapolis, Indiana, 2020-2021
Article