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. 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 v a,b tells that the valve lies close to junction a of the generic pipe (a, b); similarly v b,a tells that the valve is on the extreme b of pipe (a, b). So, the installed valves are:
, and v 7,5 . This positioning yields 4 sectors, named s 1 , s 2 , s 3 , and s 4 in Figure 1; s 2 has the greatest internal demand (ID), i.e., ID(s 2 ) = 21l/s, whereas ID(s 1 ) = 17l/s, ID(s 3 ) = 7l/s, and ID(s 4 ) = 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 (2, 3), (6,8) and (7,8) are isolated whenever a pipe in s 1 , e.g., (5,6), gets broken. Closing s 1 's boundary valves also determines the isolation of s 3 and s 4 , so U D(s 1 ) = ID(s 1 ) + ID(s 3 ) + ID(s 4 ) = 17 + 8 + 7 = 32l/s, that makes s 1 the worst isolation case in terms of unsatisfied demand; s 3 and s 4 are called unintended isolations of s 1 .
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.
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 N v , the objective function can be stated in a general fashion as min : max s {U D(s)}, and the Pareto front can be computed by a sequence of single-objective problems.
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].
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 N v 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.
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 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.