The positioning of isolation valves on water distribution networks is a hard design issue in hydroinformatics. Hydraulic engineers usually solve it by way of genetic algorithms, which do not exploit the constrained structure of the problem. Several solving approaches, based on constrained optimisation, have been developed in Artificial Intelligence, and prove that this discipline can surely have a prominent role in hydraulic networks design.
Water Distribution Systems (WDSs) are complex systems whose mission is to supply water to the communities living in their service area. A WDS is made of several components, the main ones being: a set of reservoirs feeding the WDS, a set of pipes delivering water to the system users, a set of junctions connecting two or more pipes to each other; each pipe has then a user demand to satisfy, and it can be quantified by the average water consumption (litres per second [l/s]). We illustrate these components on the toy network depicted in Figure 1. This hydraulic network has a single reservoir T , 8 junctions and 10 pipes with positive demand, plus a 0-demand pipe which connects the reservoir to the rest of the network.
Many design issues in hydraulic engineering come up as constrained optimisation problems, e.g., the design of pipes’ diameters [4], the positioning of various hydraulic devices such as quality sensors [21], valves [11], pumps [18]. Artificial Intelligence provides suitable declarative paradigms and languages to define these problems, e.g., Logic Programming [16], Answer Set Programming [14, 10], and Constraint Programming [22] among all, many dedicated algorithms, and very efficient off-the-shelf solvers [9, 23, 8, 15]. Several of these technologies have been exploited to optimise the positioning of valves, which is introduced just below; this success case shows that Artificial Intelligence also designes solutions in hydraulic engineering and extends hydroinformatics with powerful tools. 1 b 4 b 12l/s 2 b 5 b 7 b 5l/s
v1,4 4 b 2 v2,3 b
s3 s1 s2
v5,4 b5 sa isolates sb 7 b
s1 v5,7 s4 The isolation system. Failure of ageing pipes frequently occurs. In such a case, the leaking pipe is isolated on purpose, to be de-watered and fixed. Isolation is achieved by closing some of the isolation valves purposely located on the network, in such a way that the failed pipe gets disconnected from the reservoirs. In the ideal situation, each pipe would have one such valve positioned at each of its two extremes, so that only that pipe could be disconnected in case of maintenance by closing just its two valves, and it would require twice as many valves as the network pipes. However, the number of valves is limited due to cost, and their intelligent location poses a challenge, as described hereafter.
First, valves must be properly located at pipe extremes, right in adjacency to the junctions; in fact, manholes are typically available there, so junctions are accessible for maintenance purposes. Also, every pipe can get broken, thus any pipe must be isolable by closing some valves. Consequently, when all valves are closed the network should be subdivided into a set of subnets (or connected components in graph theory). We call sectors the subnets that are induced by closing all valves. The valves delimiting a sector s are the boundary valves of s, and have to be closed to isolate s whenever any pipe gets broken in it.
Figure 2 reports a feasible isolation system made of 7 valves, where va,b tells that the valve lies close to junction a of the generic pipe (a, b); similarly vb,a tells that the valve is on the extreme b of pipe (a, b). So, the installed valves are: v1,2, v1,4, v2,3, v3,6, v5,4, v6,8, and v7,5. This positioning yields 4 sectors, named s1, s2, s3, and s4 in Figure 1; s2 has the greatest internal demand (ID), i.e., ID(s2) = 21l/s, whereas ID(s1) = 17l/s, ID(s3) = 7l/s, and ID(s4) = 8l/s.
When a sector is isolated, all its users experience supply disruption that is measured by the amount of their unsatisfied demand (UD). The WDS engineers who design the network aim to reduce and equally distribute the service disruption among users in case of maintenance operations. Graph partitioning problems recall several aspects of this problem structure and they can be exploited to compute a feasible sectorization of the network; however, they are able to represent only the internal demand of the sectors, which is often lower than the whole unsatisfied demand due to its isolation.
Unintended Isolations. A sector for which all connections to the reservoirs go
through other isolated sectors will be isolated as well. Having Figure 2 at hand,
pipes (
In general we have that ID(s) ≤ U D(s), which means that the quality measure of the sectorization does not depend only on the internal demand of the sectors. To include the missing quantity and achieve the entire unsatisfied demand of a sector isolation, the unintended isolations should be modelled.
Next section defines the isolation system design as a constrained optimisation problem, then recalls related works and describes existing solution approaches in Artificial Intelligence. Section 3 shows results and Section 4 draws conclusions and future works. 2
The design of the isolation system of WDSs can be formulated as a constrained optimisation problems that consists of computing the optimal placement of a limited number of valves; the positioning should draw a sectorization of the network, so that any pipe can be isolated. What an optimal placement is may depend on several criteria that give rise to different objective functions; in particular, in the hydraulic engineering literature a bi-objective optimisation minimizes i) the maximum undelivered demand and ii) the number of valves [11]. Accordingly, having fixed a number of valves Nv, the objective function can be stated in a general fashion as min : maxs{U D(s)}, and the Pareto front can be computed by a sequence of single-objective problems. 2.1
In the literature of hydraulic engineering, a multi-objective genetic algorithm for the near-optimal design of the isolation system is described in [11]; the isolation system’s cost is also optimised by a genetic algorithm in [3]. Both cannot ensure that the found solutions are indeed the Pareto optimal.
The first mathematical model for this constrained optimisation problem was a Mixed Integer Linear Programming (MILP [17]), it integrates Graph Partitioning and Maximum Flows modules [20] and it has been further generalized in [19]. A stochastic formulation of this model has been proposed in [1]. 2.2
Two main exact approaches have been proposed in Artificial Intelligence, and in particular they are based on Logic Programming, as follows.
Constraint Logic Programming. The first exact approach for the design of the isolation system was implemented in Constraint Logic Programming on Finite Domains (CLP(FD)) [13]. It models the problem as a two-player game, and solves it with a minimax approach [2]. The moves of this game are: i) the first player places Nv valves in the network, ii) the second player selects one pipe to be damaged, iii) the first closes a set of valves isolating the damaged pipe. The cost for the first player (and reward for the second) is the undelivered demand: the total demand of all users that remain without service when the broken pipe is isolated. Sectors are built up on the fly and not explicitly defined by this approach, so no symmetry on sectors’ names is induced.
Answer Set Programming. In Artificial Intelligence, Answer Set Programming (ASP) [14, 10] is another logic paradigm that allows for solving constrained optimisation problems. Several ASP programs have been developed for the design of the isolation system [6, 5]. Some programs measure the worst isolation case by computing the reachability of each pipe from the sources, so enumerating the paths from the sources to the demand points. Other programs group the isolated pipes into sectors and compute the sectors reachability from the sources; in this way, the exponential explosion of paths is reduced at the cost of a huge symmetry on sectors’ names, however symmetry breaking constraints can be imposed and effectively help the search [5]. All these programs count a few logic rules, about 25.
The mathematical program described in Section 2.1 can be solved by branch and bound and, like the CLP(FD) and the ASP programs, provides optimal solutions. We show a computational comparison of these three methodologies in the next section. 3
The CLP(FD) and ASP programs in Section 2.2 were solved with ECLiPSe [23] and Clasp [8], respectively, whereas the MILP program in [20, 19] was solved with Gurobi [12]. These algorithms are complete, so they are able to find the optimal solutions and prove optimality.
The chart in Figure 3 shows the optimal Pareto front [2] for a real hydraulic
network, consisting of 33 pipes, and it improves the approximated front in [11]
of about the 10% for some points; notice that all exact approaches are able to
compute the very same optimal front, though computing times may be quite
different. In particular, the computational comparison in [19] shows that with a
timeout of 10′000 seconds the MILP program is solved up to 10 valves, the ASP
one up to 11, and the CLP(FD) up to 14, as shown in Figure 4. The MILP model
suffers of a huge number of symmetries, but symmetry breaking through hard
constraints has no effect [19], whereas it is very helpful in ASP and in constraint
propagation systems. The ASP programs can be improved further, as discussed
in [19]. It is worth noting that both solution approaches in Artificial Intelligence
overcome the MILP program in terms of computing time.
We summarized two existing approaches that have been developed in Artificial
Intelligence to address the isolation system design, i.e., a constrained
optimisation problem in hydraulic engineering. These approaches improved the state of
the art in the hydraulic engineering literature in terms of solution quality and
in the Operations Research literature in terms of computing time. This proved
that Artificial Intelligence provides suitable technologies to address design
issues arising in hydraulic engineering, and we believe it will be integrated more
and more into the hydroinformatics in the next future. As the results show,
exact approaches do not scale up on larger instances, so future work aims to
develop hybrid methodologies and heuristics. MILP and ASP technologies could
be coupled together to solve decompositions of the MILP model. Also genetic
algorithms could be coupled with ASP, in analogy to the work in [7]; in this way
the search capability of genetic algorithms on combinatorial spaces is enriched
with an ASP optimisation layer, whose role would be to tighten the search space.
6. M. Gavanelli, M. Nonato, A. Peano, S. Alvisi, and M. Franchini. An ASP approach
for the valves positioning optimization in a water distribution system. In F. Lisi,
editor, 9th Italian Convention on Computational Logic (CILC 2012), Rome, Italy,
volume 857 of CEUR workshop proceedings, pages 134–148, 2012.
7. M. Gavanelli, M. Nonato, A. Peano, S. Alvisi, and M. Franchini. Scheduling
countermeasures to contamination events by genetic algorithms. AI Communications,
28(
Handbook of Knowledge Representation, pages 285–316. Elsevier Science, 2008.
11. O. Giustolisi and D. A. Savi´c. Identification of segments and optimal isolation
valve system design in water distribution networks. Urban Water Journal, 7(
http://www.gurobi.com. 13. J. Jaffar and M. J. Maher. Constraint logic programming: a survey. The Journal of Logic Programming, 1920, Supplement 1(0):503 – 581, 1994. Special Issue: Ten Years of Logic Programming. 14. N. Leone. Logic programming and nonmonotonic reasoning: From theory to systems and applications. In C. Baral, G. Brewka, and J. Schlipf, editors, Logic Programming and Nonmonotonic Reasoning, volume 4483 of Lecture Notes in Computer Science, pages 1–1. Springer Berlin Heidelberg, 2007. 15. N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello.
The DLV system for knowledge representation and reasoning. ACM Transactions
on Computational Logic (TOCL), 7(
New York, Inc., New York, NY, USA, 1987. 17. R. Martin. Large Scale Linear and Integer Optimization: A Unified Approach.
Springer US, 1999.
18. I. Narayanan, V. Sarangan, A. Vasan, A. Srinivasan, A. Sivasubramaniam, B. Murt,
and S. Narasimhan. Efficient booster pump placement in water networks using
graph theoretic principles. In Green Computing Conference (IGCC), 2012
International, pages 1–6, June 2012.
19. A. Peano. Solving Real-Life Hydroinformatics Problems with Operations Research
and Artificial Intelligence. PhD thesis, University of Ferrara, 2015.
20. A. Peano, M. Nonato, M. Gavanelli, S. Alvisi, and M. Franchini. A bilevel mixed
integer linear programming model for valves location in water distribution systems.
In S. Ravizza and P. Holborn, editors, 3rd Student Conference on Operational
Research, volume 22 of OpenAccess Series in Informatics (OASIcs), pages 103–112,
Dagstuhl, Germany, 2012. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
21. S. Rathi and R. Gupta. Sensor placement methods for contamination detection
in water distribution networks: A review. Procedia Engineering, 89(0):181 – 188,
2014. 16th Water Distribution System Analysis Conference, {WDSA2014} Urban
Water Hydroinformatics and Strategic Planning.
22. F. Rossi, P. van Beek, and T. Walsh. Handbook of Constraint Programming.
Foundations of Artificial Intelligence. Elsevier Science, 2006.
23. J. Schimpf and K. Shen. Eclipse - from LP to CLP. TPLP, 12(