=Paper=
{{Paper
|id=None
|storemode=property
|title=An ASP Approach for the Optimal Placement of the Isolation Valves in a Water Distribution System
|pdfUrl=https://ceur-ws.org/Vol-926/paper7.pdf
|volume=Vol-926
|dblpUrl=https://dblp.org/rec/conf/aiia/PeanoG12
}}
==An ASP Approach for the Optimal Placement of the Isolation Valves in a Water Distribution System==
https://ceur-ws.org/Vol-926/paper7.pdf
33
An ASP Approach for the Optimal Placement of
the Isolation Valves in a Water Distribution
System
Andrea Peano
Supervisor: Marco Gavanelli
EnDiF, Università degli Studi di Ferrara
via G. Saragat 1 – 44122 Ferrara, Italy
andrea.peano@unife.it
1 Introduction
My Ph.D. Thesis relates to real-life optimization problems in the hydraulic en-
gineering field. More precisely, with the collaboration of computer scientists,
operational researchers and hydraulic engineers, I investigate and exploit poten-
tialities of various Operational Research and Artificial Intelligence techniques in
order to achieve good (and, whenever possible, optimal) solutions for those par-
ticular design issues of the urban hydraulic network that can be effectively mod-
elled as known combinatorial optimization problems. Furthermore, such design
issues often require to devise new specialized variants of the known combinatorial
optimization problems.
For example, the problem of minimizing the impact of a contamination in a
hydraulic network can be seen, under opportune assumptions, as a variant of the
well known Multiple Traveling Salesman Problem (MTSP); since the quality of
feasible solutions must be computed through a burdensome hydraulic simulation,
such optimization problem was addressed by us by means of several genetic
algorithms [6]. In particular, in [6], we proposed a novel genetic encoding for
the MTSP for which we defined new genetic crossover operators based on ad
hoc mixed integer linear programming (sub-)optimizations, obtaining a hybrid
genetic algorithm.
Another real-life combinatorial optimization problem which is a typical issue
during the design of a hydraulic network is finding the optimal positioning of
a limited number of isolation valves on the network. Up to now, we exploited
two different technologies, following two independent approaches: in the first we
modelled the above mentioned problem by means of a Bilevel (Mixed Integer)
Linear Programming [3] formalization, discussed in [13]; I presented the study
at the 3rd Student Conference on Operational Research (SCOR 2012). In the
second approach, we addressed such optimization problem by defining several
Answer Set Programming (ASP)[1, 11, 8] programs, discussed in [5]. Both the
optimization approaches compute the globally optimum placement of the valves.
In the next section I will briefly describe the problem of the isolation valve
placement on hydraulic networks and the ASP approach designed to solve it.
34
2 The Isolation Valves Location Problem
Water Distributions Systems (WDSs) are strategic urban infrastructures. Their
planning is, in turn, a strategic task in terms of costs control and to assure a
fair degree of reliability. For example, during the design of a water distribution
network, one of the choices is the design of the isolation system. It is a real-life
problem for hydraulic engineers, and in recent years it has been studied through
computational methods in the hydroinformatics literature [9, 4].
A water distribution system has the main objective of providing water to
homes and facilities that require it. The water distribution network can be
thought of as a labelled indirected graph, in which the edges represent the pipes
in the network. There is at least one special node that represents the source of
water (node 1 in Figure 1), and the users’ homes are connected to the edges. For
each edge, we assume to have knowledge about the average amount of water (in
litres per second) that is drawn by the users insisting on that edge (during the
day); such value is the label associated to the edge, and it is called the users’
demand.
v2,3
T 1 v1,2 2 3
3l/s 6l/s v3,6
v1,4
1l/s 4l/s 5l/s
v5,4
6
4 2l/s 5 1l/s v6,8
4l/s 1l/s
v5,7
7 5l/s 8
Fig. 1. A water distribution network with valves
The isolation system is mainly used during repair operations: in case some
pipe is damaged, it has to be fixed or substituted. However, no repair work can
be done while the water is flowing at high pressure in the pipe: first the part
of the network containing the broken pipe should be de-watered, then workers
can fix the pipe. The de-watering is performed by closing an opportune set
of isolation valves (that make up the so-called isolation system of the water
distribution network) so that the damaged pipe is disconnected from the sources.
For example, in Figure 1, if the edge connecting nodes 2 and 3 (let us call it e2,3 )
is broken, workers can close valves v2,3 and v3,6 and de-water the broken pipe.
Of course, during this pipe substitution the users that take water from edge e2,3
cannot be serviced. The usual measure of disruption is the undelivered demand:
in this case, it corresponds to the demand of the users insisting on the broken
pipe, i.e., 6l/s.
However, we are not always this lucky: in case the damaged pipe is e7,8 ,
workers will have to close valves v5,7 and v6,8 , de-watering pipes e7,8 and e6,8 ,
35
with a total cost of 5 + 1 = 6l/s. In fact, the minimum set of pipes that will
be de-watered is that belonging to the so-called sector of the broken pipe, i.e.,
the set of pipes encircled by a same set of valves. But there can be even worse
situations: if the broken pipe is e2,5 , workers have to close valves v1,2 and v5,4 ,
which means disconnecting all the pipes except e1,4 and e4,5 , with an undelivered
demand of 3 + 4 + 6 + 5 + 1 + 4 + 5 + 1 = 29l/s. Notice in particular that the edges
e2,3 , e7,8 and e6,8 are disconnected in this way, although they do not belong to
the same sector as the broken pipe. This effect is called unintended isolation,
and usually means that the isolation system was poorly designed.
One common value used by hydraulic engineers [9] to measure the quality
of the isolation system is the undelivered demand in the worst case. In the
example of Figure 1, the worst case happens when the broken pipe is in the set
{e1,2 , e2,5 , e5,6 , e5,7 }, and the related suppy disruption is 29l/s, as above.
In a previous work, [2] developed a system, based on Constraint Logic Pro-
gramming [10] on Finite Domains (CLP(FD)), that finds the optimal positioning
of a given number of valves in a water distribution network. The assignments
found by [2] improved the state-of-the-art in hydraulic engineering for this prob-
lem, finding solutions with a lower (worst-case) undelivered demand than the
best solutions known in the literature of hydraulic engineering [9], obtained
through genetic algorithms.
In the current work, we address the same problem in Answer Set Program-
ming [1, 11, 8], which is a suitable technology to address combinatorial graph
problems[12], and, in particular, we have already defined two different ASP pro-
grams [5]. One program explicitly defines the sectors as clusters of (isolated)
pipes and minimizes the undelivered demand of the worst sector; instead, in the
other program, sectors are left implicit and the aim is to maximize the minimum
satisfied demand in case of pipe isolation, by considering that a pipe is isolated
if it is not reachable from any source. In the next section we show the most
important results obtained by first experiments.
3 Results
The first experiments, presented in [5], show, in general, that the developed
programs take more computation time than the CLP(FD) approach [2]. However,
we must say that the CLP(FD) model was developed by two CLP experts,
during some person-months and was trimmed for efficiency. Instead, the two
ASP formulations were mainly developed by a first-year PhD student in about
one week; this shows that ASP is very intuitive and easy to understand even
for non experts, that it is indeed very declarative. The two implemented ASP
programs consist of respectively about 20 and 25 rules, which shows that ASP
is a very interesting technology for rapid prototyping.
Experiments have been performed on a Intel based architecture with two
P8400 CPUs; as ASP solver we used the Potassco’s solver Clasp [7]. The two
programs have been optimized using a real-life instance based on the Apulian
hydraulic network [9] (Figure 2) and varying the number of available isolation
valves.
36
3 2
9 T
10 1 19
4 5
18 23
11 6 17
16 21
13 7
12 15
22 8 14 20
Fig. 2. The Apulian hydraulic network
Figure 3 shows the optimization performance of the two ASP programs (the
one based on sectors and the one that, instead, does not define sectors) for
several number of available valves. In particular, the better effectiveness of the
sector-based program can be noticed.
Fig. 3. Computing times of the optimization processes of the two ASP programs
4 Future Work
In future work, we plan to improve the sector-based ASP program by defining
opportune rules in order to break the symmetries determined by the current
formalization, and we will experiment the resulting program also with other
available ASP solvers. Another appealing challenge is to compute the solution
that minimizes the undelivered demand of the worst sector as well as the undeliv-
ered demands of the other (no worst) sectors, which are not actually optimized
neither by our current MILP formalization [13] nor by the CLP(FD) one [2].
We are also interested in trying to integrate the ASP programs with a CLP
approach, to take advantage of the strengths of the two approaches. Finally, I
plan to delve into the ASP theory and techniques in order to consolidate my
competence in such Artificial Intelligence field.
37
Acknowledgements This work was partially supported by EU project ePolicy, FP7-
ICT-2011-7, grant agreement 288147. Possible inaccuracies of information are under the
responsibility of the project team. The text reflects solely the views of its authors. The
European Commission is not liable for any use that may be made of the information
contained in this paper.
References
1. Baral, C.: Knowledge representation, reasoning and declarative problem solving.
Cambridge University Press (2003)
2. Cattafi, M., Gavanelli, M., Nonato, M., Alvisi, S., Franchini, M.: 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), http://arxiv.org/abs/1109.1248
3. Colson, B., Marcotte, P., Savard, G.: Bilevel programming: A survey. 4OR: A
Quarterly Journal of Operations Research 3, 87–107 (2005)
4. Creaco, E., Franchini, M., Alvisi, S.: Optimal placement of isolation valves in water
distribution systems based on valve cost and weighted average demand shortfall.
Water Resources Management 24, 4317–4338 (2010)
5. Gavanelli, M., Nonato, M., Peano, A., Alvisi, S., Franchini, M.: An ASP approach
for the valves positioning optimization in a water distribution system. In: Lisi, F.
(ed.) 9th Italian Convention on Computational Logic (CILC 2012), Rome, Italy.
CEUR workshop proceedings, vol. 857, pp. 134–148 (2012)
6. Gavanelli, M., Nonato, M., Peano, A., Alvisi, S., Franchini, M.: Genetic algorithms
for scheduling devices operation in a water distribution system in response to con-
tamination events. In: Hao, J.K., Middendorf, M. (eds.) Evolutionary Computation
in Combinatorial Optimization, Lecture Notes in Computer Science, vol. 7245, pp.
124–135. Springer Berlin / Heidelberg (2012)
7. Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Schneider,
M.: Potassco: The Potsdam answer set solving collection. AI Communications
24(2), 105–124 (2011)
8. Gelfond, M.: Answer sets. In: Handbook of Knowledge Representation, chap. 7.
Elsevier (2007)
9. Giustolisi, O., Savić, D.A.: Identification of segments and optimal isolation valve
system design in water distribution networks. Urban Water Journal 7(1), 1–15
(2010)
10. Jaffar, J., Maher, M.J.: Constraint logic programming: A survey. J. Log. Program.
19/20, 503–581 (1994)
11. Leone, N.: Logic programming and nonmonotonic reasoning: From theory to sys-
tems and applications. In: Baral, C., Brewka, G., Schlipf, J. (eds.) Proceedings
of the 9th International Conference on Logic Programming and Nonmonotonic
Reasoning (LPNMR’07), Lecture Notes in Computer Science, vol. 4483. Springer
(2007)
12. Niemelä, I.: Logic programs with stable model semantics as a constraint program-
ming paradigm. Annals of Mathematics and Artificial Intelligence 25, 241–273
(1999)
13. Peano, A., Nonato, M., Gavanelli, M., Alvisi, S., Franchini, M.: A Bilevel Mixed
Integer Linear Programming Model for Valves Location in Water Distribution Sys-
tems. In: Ravizza, S., Holborn, P. (eds.) 3rd Student Conference on Operational
Research. OpenAccess Series in Informatics (OASIcs), vol. 22, pp. 103–112. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2012)