Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality
Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality
复制标题
解决配水管网设计问题的全局最优的有效放宽和分区方案
DOI：
--
复制
发表时间：
2001
影响因子：
1.8
通讯作者：
G. Loganathan
中科院分区：
文献类型：
--
作者：
H. Sherali;Shivaram Subramanian;G. Loganathan
在本文中，我们解决的问题，设计一个配水网络，包括扩大现有系统的情况下，满足指定的流量需求，在规定的压头要求的全局优化程序的发展。所提出的方法显着改善了以前的方法Sherali等人。（1998）通过采用更紧密的多面体松弛，更有效的分区策略与最大生成树为基础的分支变量选择过程。从文献中的三个标准测试问题的计算经验，以评估所提出的程序。对于所有这些问题，得到了在10−4%的公差内和/或在1$最优性内的已证明的全局最优解。特别是，河内和纽约的测试网络的两个较大的情况下，解决了全球最优的文献中的第一次。一个新的真实的网络设计测试问题的基础上，城市的布莱克斯堡供水系统也提供了包括在可用的测试用例库，并给出了相关的计算结果。
In this paper, we address the development of a global optimization procedure for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach significantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning strategies in concert with a maximal spanning tree-based branching variable selection procedure. Computational experience on three standard test problems from the literature is provided to evaluate the proposed procedure. For all these problems, proven global optimal solutions within a tolerance of 10−4% and/or within 1$ of optimality are obtained. In particular, the two larger instances of the Hanoi and the New York test networks are solved to global optimality for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results are presented.