An ASP Approach for the Optimal Placement of the Isolation Valves in a Water Distribution System

Introduction

My Ph.D. Thesis relates to real-life optimization problems in the hydraulic engineering field. More precisely, with the collaboration of computer scientists, operational researchers and hydraulic engineers, I investigate and exploit potentialities of various Operational Research and Artificial Intelligence techniques in order to achieve good (and, whenever possible, optimal) solutions for those particular design issues of the urban hydraulic network that can be effectively modelled 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.

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.

T

1 v1,2

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, 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 Programming [ 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 problem, 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 Programming [ 1, 11, 8 ], which is a suitable technology to address combinatorial graph problems[ 12 ], and, in particular, we have already defined two different ASP programs [ 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. 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 undelivered 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. Acknowledgements This work was partially supported by EU project ePolicy, FP7ICT-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 placement 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 contamination 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´c, 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 systems 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. Niemela¨, I. : Logic programs with stable model semantics as a constraint programming 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 Systems . 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 )