=Paper=
{{Paper
|id=Vol-1473/paper3
|storemode=property
|title=The Isolation System Design in
Hydraulic Networks
|pdfUrl=https://ceur-ws.org/Vol-1473/paper3.pdf
|volume=Vol-1473
|dblpUrl=https://dblp.org/rec/conf/aiia/GavanelliNP15
}}
==The Isolation System Design in
Hydraulic Networks==
https://ceur-ws.org/Vol-1473/paper3.pdf
The Isolation System Design
in Hydraulic Networks
Marco Gavanelli, Maddalena Nonato, and Andrea Peano
Engineering Department - University of Ferrara,
Via Saragat 1 - 44121 Ferrara - Italy,
{marco.gavanelli,maddalena.nonato,andrea.peano}@unife.it
Abstract. The positioning of isolation valves on water distribution net-
works 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 Intelli-
gence, and prove that this discipline can surely have a prominent role in
hydraulic networks design.
Keywords: hydroinformatics, isolation system design
1 Introduction
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 optimisa-
tion problems, e.g., the design of pipes’ diameters [4], the positioning of various
hydraulic devices such as quality sensors [21], valves [11], pumps [18]. Artifi-
cial 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.
T
1 b
2 b b 3 1
v1,2
2
v2,3
3b
b b
4l/s 7l/s
v1,4 s3 v3,6
12l/s 5l/s 1l/s
s2
s1
4 b 5 b b
6 4b
v5,4
5 6
b b
9l/s 2l/s
v6,8
s1
5l/s 2l/s sa sb
isolates
v5,7 s4
7 b b
8
7 b b 8
6l/s
Fig. 1. A toy network Fig. 2. A feasible sectorization
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 engi-
neers 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 ex-
ploited 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 s1 , e.g., (5, 6), gets
broken. Closing s1 ’s boundary valves also determines the isolation of s3 and s4 ,
so U D(s1 ) = ID(s1 ) + ID(s3 ) + ID(s4 ) = 17 + 8 + 7 = 32l/s, that makes s1
the worst isolation case in terms of unsatisfied demand; s3 and s4 are called
unintended isolations of s1 .
In general we have that ID(s) ≤ U D(s), which means that the quality mea-
sure of the sectorization does not depend only on the internal demand of the
sectors. To include the missing quantity and achieve the entire unsatisfied de-
mand 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 Optimising the Valves Positioning
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 lim-
ited 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 Related Works
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 Parti-
tioning 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 Solution Approaches in Logic Programming
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 op-
timisation 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 symme-
try 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 Results
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.
Fig. 3. Pareto fronts in [2] Fig. 4. Computational comparison in [19]
4 Conclusion
We summarized two existing approaches that have been developed in Artificial
Intelligence to address the isolation system design, i.e., a constrained optimisa-
tion 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 is-
sues 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.
References
1. M. Bruni, P. Beraldi, and D. Conforti. A stochastic programming approach for
the strategic valve locations problem in a water distribution system. Procedia -
Social and Behavioral Sciences, 108(0):129 – 138, 2014. Operational Research for
Development, Sustainability and Local Economies.
2. M. Cattafi, M. Gavanelli, M. Nonato, S. Alvisi, and M. Franchini. Optimal place-
ment of valves in a water distribution network with CLP(FD). Theory and Practice
of Logic Programming, 11(4-5):731–747, 2011.
3. E. Creaco, M. Franchini, and S. Alvisi. Optimal placement of isolation valves
in water distribution systems based on valve cost and weighted average demand
shortfall. Water Resources Management, 24(15):4317–4338, 2010.
4. M. Franchini. Un excursus sugli algoritmi per la progettazione e la riabilitazione
delle reti di distribuzione idrica. L’Acqua, 2:15 – 22, 2010.
5. M. Gavanelli, M. Nonato, and A. Peano. An ASP approach for the valves position-
ing optimization in a water distribution system. Journal of Logic and Computation,
2013. Accepted for publication.
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 coun-
termeasures to contamination events by genetic algorithms. AI Communications,
28(2):259–282, 2015.
8. M. Gebser, B. Kaufmann, and T. Schaub. Conflict-driven answer set solving: From
theory to practice. Artificial Intelligence, 187-188:52–89, Aug. 2012.
9. Gecode Team. Gecode: Generic constraint development environment, 2006. Avail-
able from http://www.gecode.org.
10. M. Gelfond. Answer sets. In F. van Harmelen, V. Lifschitz, and B. Porter, editors,
Handbook of Knowledge Representation, pages 285–316. Elsevier Science, 2008.
11. O. Giustolisi and D. A. Savić. Identification of segments and optimal isolation
valve system design in water distribution networks. Urban Water Journal, 7(1):1–
15, 2010.
12. Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2014.
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 sys-
tems and applications. In C. Baral, G. Brewka, and J. Schlipf, editors, Logic Pro-
gramming and Nonmonotonic Reasoning, volume 4483 of Lecture Notes in Com-
puter 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(3):499–562, July 2006.
16. J. W. Lloyd. Foundations of Logic Programming; (2nd ext. ed.). Springer-Verlag
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 Inter-
national, 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. Foun-
dations of Artificial Intelligence. Elsevier Science, 2006.
23. J. Schimpf and K. Shen. Ecli pse - from LP to CLP. TPLP, 12(1-2):127–156, 2012.