Control and Optimisation seminar – Aly-Joy Ulusay (Imperial-Civil Engineering)

Title

A nested column-and-constraint generation algorithm for the resilient design of water distribution networks

Abstract

This work investigates the problem of maximizing the ability of water distribution networks (WDN) to maintain continuous customer supply following the detection and isolation of a pipe failure. We present a tri-level defender–attacker–defender (DAD) formulation, where the defender installs new links (upper-level), the attacker then selects a failure scenario (mid-level) and the defender finally adopts a hydraulically balanced incident response strategy (lower-level) to maximize total supplied demand. Since the lower-level MINLP combines binary control (valve status) variables and non-convex hydraulic constraints, the DAD problem cannot directly be solved using available methods from, e.g., the power grid transmission expansion planning literature. Instead, we introduce linear relaxations of the non-convex constraints and present a tailored nested column-and-constraint generation (CCG) algorithm to solve the relaxed tri-level problem. This provides an upper bound on the original problem, while a feasible solution (and lower bound) is obtained by performing a critical link analysis (CLA) on the nested CCG-computed design. The proposed method is applied to solve the optimal expansion problem for a large-scale operational WDN in the UK, reducing computational time by several orders of magnitude compared to performing an exhaustive CLA-based search. The nested CCG-computed designs, shown to be nearly optimal in this large-scale instance, significantly improve the WDN’s worst-case performance by efficiently rerouting flows through the network.

Bio