Development and Application of the DIRECT Algorithm for Leak Detection in Water Distribution Systems

The Dividing Rectangles (DIRECT) search is a deterministic, derivative-free, global search algorithm. The algorithm searches for the global minimum by recursive space partitioning, essentially grouping similar regions within the decision space and selecting a sample from each group. The DIRECT algorithm was initially designed for continuous problems, but has since been modified to allow for integer variable types. Though DIRECT has been previously used for discrete numbers, the algorithm has not been extended to other discrete variable types, such as graph nodes or multi-dimensional points. This research further extends the DIRECT algorithm to use a mix of continuous and discrete variables, including connected graph nodes. In this paper, the algorithm is applied to leak detection problems in water distribution systems (WDSs), which involve both discrete network nodes and continuous leak magnitudes. In addition, the DIRECT algorithm is parallelized using a master-worker paradigm and tested using cluster resources for a moderate number of processors. The generalization and abstraction of the DIRECT algorithm presented in this research will enable the application of DIRECT to a wider class of problems than previously possible.