《Sustainable Futures》：Application of benders decomposition for the solution of non-linear waste water treatment network design problem
编辑推荐：
为解决气候变化背景下水资源短缺与污水处理网络优化设计难题，研究人员针对废水处理网络设计（WWTND）这一非线性优化问题，开展了一项应用Benders分解法的研究。该研究在考虑居民区与处理厂距离、未来人口预测等因素的基础上，对现有网络扩容或新建的成本进行了建模，并提出了“先线性化后分解”（FLTD）和“先分解后线性化”（FDTL）两种策略，通过在卢森堡地区的案例应用，验证了其在计算效率方面的优越性。这项研究为大型基础设施网络的精确优化设计提供了新的方法论。
气候变化引发的干旱频发，正迫使全球各地重新审视水资源的循环利用。在这一背景下，废水处理（WWT）作为缓解水资源短缺、保护环境的关键策略，其重要性日益凸显。然而，设计一个高效、经济的废水处理网络（WWTN）并非易事。这需要权衡诸多复杂因素：居住区与污水处理厂（WWTP）之间的远近、未来城镇人口的增长预测、以及扩建现有管网或新建设施所需的庞大成本。更棘手的是，诸如管道铺设和污水处理厂建设的成本往往是非线性的，它们与网络中处理和产生的污水量紧密相关。传统的解决思路，无论是依赖启发式算法还是仿真模拟，往往难以保证解决方案的最优性，或者因模型过于复杂而难以推广。那么，是否存在一种方法，能够精确求解这个非线性的废水处理网络设计（WWTND）问题，并灵活应用于不同地区的实际规划呢？
近日，一项发表在《Sustainable Futures》上的研究为这一难题提供了创新的解答。来自帝国理工学院的研究团队Pantelis Broukos、Antonios Fragkogios、Michalis Fragkiadakis和Nilay Shah，将经典的数学优化方法——Benders分解，创新性地应用于废水处理网络设计问题。他们不仅攻克了直接求解非线性原模型的挑战，还系统性地对比了两种全新的求解策略：“先线性化，后分解”（FLTD）与“先分解，后线性化”（FDTL），并在卢森堡的一个实际案例中验证了其高效性。此外，研究团队还通过引入有效不等式（Valid Inequalities, VIs）来加强主问题，显著加速了算法的收敛速度。这项工作的意义在于，它首次为原始的非线性WWTND问题提供了基于Benders分解的精确求解框架，为大型基础设施网络的优化设计开辟了新路径，并且该方法可被推广至固体废物收集、能源配送等具有类似非线性成本结构的网络设计问题中。
为开展此项研究，作者主要运用了以下几个关键技术方法：首先，构建了混合整数非线性规划（MINLP）模型来表述WWTND问题，其中包含了污水处理厂扩建与运营维护（O&M）的非线性凹成本函数。其次，采用了分段线性化方法，结合特殊有序集类型2（SOS2）变量及限制基变量约束，对非线性成本函数进行线性逼近。最后，核心方法是应用Benders分解算法，包括其经典形式（用于线性问题）和广义形式（GBD，用于非线性规划），并将问题分解为松弛主问题（RMP）和原始子问题（PSP）进行迭代求解。研究基于卢森堡地区的实际人口、地理及现有设施数据构建了案例。
研究结果
1. 数学建模与问题分解
研究人员首先将WWTND问题构建为一个混合整数非线性规划（MINLP）模型，即非线性原始问题（NLOP）。该模型的目标函数是最小化包含管道建设与维护成本、以及污水处理厂（WWTP）非线性扩建成本与运营维护（O&M）成本在内的总成本。模型约束确保了污水收集、输送与处理能力的供需平衡与逻辑关联。为求解此大规模复杂问题，研究引入了Benders分解法，并探索了两种实施路径：FLTD（先对NLOP进行分段线性化，再对得到的线性化原问题（LOP）应用Benders分解）和FDTL（先对NLOP直接应用Benders分解，再在子问题中进行线性化）。
2. 两种策略的性能对比
研究在卢森堡的实际案例中对比了FLTD和FDTL两种策略。结果表明，虽然两种策略都能求得全局最优解，但FDTL策略在计算效率上更具优势。这主要是因为FDTL策略在分解步骤中更好地利用了问题的结构，使得子问题规模更小、更易求解。
3. 有效不等式的加速效果
为了进一步提升FDTL策略的求解速度，研究人员开发并加入了针对该WWTND问题的有效不等式（VIs）到松弛主问题（RMP）中。这个加速变体（FDTL_VI）通过强化RMP的松弛，提前排除了许多不可行解，从而生成了质量更高的下界。结果显示，引入VIs显著减少了Benders分解算法所需的迭代次数和总计算时间，同时保持了解的最优性。
4. 方法论的可推广性
作者指出，所提出的方法框架并不局限于污水处理网络设计。其核心是处理具有非线性、空间依赖成本的网络设计问题。因此，该方法可被直接适配于其他类型的基础设施网络，如固体废物收集、能源配送和区域供热系统。在这些应用中，污水处理厂对应于能源生产设施，管道对应于输电线路，尽管流向可能相反，但问题的基本数学结构保持一致。
结论与讨论
本研究的核心结论是，Benders分解法能够有效地用于求解非线性的废水处理网络设计问题，并且“先分解，后线性化”（FDTL）策略相比“先线性化，后分解”（FLTD）策略在计算上更为高效。通过引入针对性的有效不等式（VIs），可以进一步大幅提升算法的收敛速度。
这项研究的重要意义体现在三个方面：首先，在方法论上，这是首次将经典的Benders分解法直接应用于原始的非线性WWTND模型，而不依赖于事前的全局线性化，为处理此类非凸优化问题提供了新的精确求解工具。其次，在实践上，研究通过真实的卢森堡案例验证了方法的可行性与优越性，为区域性的水务基础设施规划提供了科学的决策支持。最后，在推广价值上，研究所开发的框架具有高度的通用性，其核心思想可用于解决众多其他公共基础设施网络的优化设计难题，为推进城市与区域的可持续发展提供了有力的数学模型与方法论支撑。
该研究成功地将先进的运筹学优化技术与实际的环境工程问题相结合，不仅解决了污水处理领域的一个具体优化难题，也为其背后广泛存在的、具有非线性成本和复杂约束的网络设计问题提供了可复制的解决方案范本。
