Journal of Algorithms and Optimization                  
Journal of Algorithms and Optimization(JAO)
Development and Application of the DIRECT Algorithm for Leak Detection in Water Distribution Systems
Full Paper(PDF, 625KB)
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.
Keywords:DIRECT; Dividing Rectangles Search; Water Distribution Systems; Leak Detection
Author: M. N. Jasper1, E. D. Brill1, R. Ranjithan1, G. Mahinthakumar1
1.Dept. of Civil, Construction, and Environmental Engineering, North Carolina State Univ., Campus Box 7908, Raleigh, NC 27695, USA
  1. D. R. Jones, C. D. Perttunen, and B. E. Stuckman, “Lipschitzian optimization without the lipschitz constant,” Journal of Optimization Theory and Application, vol. 79, no. 1, pp. 157-181, Oct. 1993.
  2. J. M. Gablonsky, “Modifications of the DIRECT Algorithm,” North Carolina State University, 2001.
  3. D. R. Jones, “Direct Global Optimization Algorithm,” in The Encyclopedia or Optimization, Kluwer Academic, 1999, pp. 725-735.
  4. A. Serani, G. Fasano, G. Liuzzi, S. Lucidi, U. Iemma, E. F. Campana, F. Stern, and M. Diez, “Ship hydrodynamic optimization by local hybridization of deterministic derivative-free global algorithms,” Applied Ocean Research, vol. 59, pp. 115-128, Sept. 2016.
  5. J. Shen, S. Dusmez, and A. Khaligh, “Optimization of Sizing and Battery Cycle Life in Battery/Ultracapacitor Hybrid Energy Storage Systems for Electric Vehicle Applications,” IEEE Transactions on Industrial Informatics, vol. 10, no. 4, pp. 2112-2121, Nov. 2014.
  6. D. di Serafino, G. Liuzzi, V. Piccialli, F. Riccio, and G. Toraldo, “A Modified DIviding RECTangles Algorithm for a Problem in Astrophysics,” Journal of Optimization Theory and Applications, vol. 151, no. 1, pp. 175-190, Oct. 2011.
  7. D. Lv and B. Goodwine, “Pancreas Modeling from IVGTT Data Using A Deterministic Optimal Search Method,” in 2009 IEEE International Conference on Bioinformatics and Biomedicine, Washington, DC, 2009.
  8. T. D. Panning, L. T. Watson, N. A. Allen, K. C. Chen, C. A. Shaffer, and J. J. Tyson, “Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle,” Journal of Global Optimization, vol. 40, no. 4, pp. 719-738, Apr. 2008.
  9. M. N. Jasper, “Development and Application of the DIRECT Algorithm for Leak Detection in Water Distribution Systems,” North Carolina State University, 2014.
  10. J. D. Griffen and T. G. Kolda, “Asynchronous parallel hybrid optimization combining DIRECT and GSS,” Optimization Methods and Software, vol. 25, no. 5, pp. 797-817, 13 Aug., 2009.
  11. J. He and L. T. Watson, “Dynamic data structures for a direct search algorithm,” Computational Optimzation and Applications, vol. 23, no. 1, pp. 5-23, Oct. 2002.
  12. J. He, A. Verstak, L. T. Watson, and M. Sosonkina, “Design and implementation of a massively parallel version of DIRECT,” Computational Optimization and Applications, vol. 40, no. 2, pp. 217-245, June 2008.
  13. J. He, L. T. Watson, and M. Sosonkina, “Algorithm 897: VTDIRECT95: Serial and parallel codes for the global optimization algorithm direct,” ACM Transactions on Mathematical Software (TOMS), vol. 36, no. 3, pp. 1-24, July 2009.
  14. R. Puust, Z. Kapelan, D. A. Savic, and T. Koppel, “A review of methods for leakage management in pipe networks,” Urban Water Journal, vol. 7, no. 1, pp. 25-45, Feb. 2010.
  15. L. A. Rossman, “The EPANET Programmer’s Toolkit for Analysis of Water Distribution Systems,” in 29th Annual Water Resources Planning and Management Conference, 2004.
  16. L. A. Rossman, “EPANET 2 Users Manual,” US EPA, Cincinatti, OH, 2000.
  17. J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509-517, Sept. 1975.
  18. A. Ostfeld and J. G. Uber, “The Battle of the Water Sensor Networks (BWSN): A Design Challenge for Engineers and Algorithms,” Journal of Water Resources Planning and Management, vol. 134, pp. 556-568, Nov. 2008.
  19. W. Gropp, E. Lusk, and R. Thakur, Using MPI-2: Advanced Features of the Message-Passing Interface, MIT Press, 1999.
  20. C. A. Baker, L. T. Watson, B. Grossman, W. H. Mason, and R. T. Haftka, “Parallel Global Aircraft Configuration Design Space Exploration,” International Journal of Computer Research, vol. 10, no. 4, pp. 501-515, 28 June, 2001.