Answer Set Programming (ASP)

An ASP Approach for the Valves Positioning Optimization in a Water Distribution System

Marco Gavanelli and Andrea Peano

An ASP approach for the valve placement problem was first proposed in [3], then extended in [2].

The valve placement problem and one of the available instances (the Apulian network) were proposed in [4]. The first exact approach consists of a CLP(FD) program [1].

Also, a mixed integer linear programming formulation was proposed for this problem [5]; the source package will be soon online.

In this web page you can download three different ASP encodings, plus three instances, and they are implemented in Clingo .

ASP encoding based on Pipe Reachability

pipe_reach.asp : the core of this approach. It defines, for each pipe, a set of valves that can isolate it. The isolation is achieved through the concept "reachability" of pipes from the tanks.
pipe_isolation.asp : it is an extension of the pipe_reach program that minimizes the undelivered demand in the worst isolation case in terms of isolated pipe.
extended_sect.asp : it is an other extension of the pipe_reach program, which explicitly defines the "extended sectors" as "groups of pipes" that share the same isolation state varying the isolated pipe, and it minimizes the undelivered demand of the greater extended sector.

We call the ASP program consisting of (1)+(2) the "Pipe Isolation" encoding, and the program consisting of (1)+(3) the "Extended Sectors" encoding. These two encodings were first proposed in [3].

ASP encoding based on Sectors

sectors.asp : it draws the "sectors" as clusters of "adjacent" pipes by exploiting information about the existence of valves between them. We call this program "Sectors" encoding.

All the previous ASP encodings are compatible with the instance format proposed for the ASP Competition 2013.

Instances

apulian.asp : the instance of the "Apulian" distribution network. Note that, in order to have integer weights, all weights were multiplied by 10 with respect to the instance shown in [4].
realtown.asp : the instance of another real-life network, called "Realtown".
anytown.asp : the instance of benchmark network widely used in the hydraulic engineering literature, called "Anytown".

Usage

To use the Pipe Isolation encoding you can inoke:

clingo -c nv=<number of valves> pipe_reach.asp pipe_isol.asp <instance>

and for the Extended Sectors encoding:

clingo -c nv=<number of valves> [-c sdim=<number of sectors>] pipe_reach.asp extended_sect.asp <instance>

Where sdim is the maximum number of sectors. If omitted, the default value is sdim=nv.

To use the Sectors encoding you can invoke:

clingo -c nv=<number of valves> [-c sdim=<number of sectors>] sectors.asp <instance>

Outcome

The output of the optimisation process consists of several atoms, depending on the predicates defined by the encodings, and the directives contained in the "display" block (at the end of the encodings).
Here a part of the output of the optimisation that uses the Extended Sectors encoding and the Apulian network:

Answer: 6
valves_number(5) valve(8,22) valve(1,5) valve(1,19) valve(1,2) valve(6,4) uniqueMax(5) maxUnsatDem(e(21,23),70)
maxUnsatDem(e(20,21),129) maxUnsatDem(e(19,23),137) maxUnsatDem(e(18,19),62) maxUnsatDem(e(17,21),94)
maxUnsatDem(e(17,18),81) maxUnsatDem(e(16,17),54) maxUnsatDem(e(15,16),41) maxUnsatDem(e(14,20),138)
maxUnsatDem(e(14,15),27) maxUnsatDem(e(8,14),107) maxUnsatDem(e(7,15),117) maxUnsatDem(e(7,8),30)
maxUnsatDem(e(6,16),129) maxUnsatDem(e(6,7),36) maxUnsatDem(e(5,18),73) maxUnsatDem(e(5,6),63) maxUnsatDem(e(1,5),66)
maxUnsatDem(e(1,19),95) 
Optimization: 1549 
OPTIMUM FOUND

Models      : 1     
  Enumerated: 6
  Optimum   : yes
Optimization: 1549 
Time        : 4.580
  Prepare   : 0.120
  Prepro.   : 0.030
  Solving   : 4.430

The positioning of valves is represented by the atoms of the form valve/2. In particular, valve(8,22) means that the valve is positioned on the pipe (8,22), close to the junction 8; instead, valve(22,8) means that the valve is positioned close to 22.

Tighter bounds on sdim

The number sdim affects the optimisation performance, and should be set as low as possible. The tightest bound is obviously the maximum number of sectors that one can achieve given nv, and it can be computed through an ad-hoc optimisation procedure. Another straightforward bound on the number of sectors is given by the following formula:

sdim=N_c + (nv−nv_min)

(1)

nv_min is the minimum number of valves necessary to disconnect the entire network from tanks (it is simply the sum of cardinality of tank nodes).
N_c is the number of connected components obtained once the network is disconnected from tanks. We report the Eq. 1 for the previous instances:

Apulian

Realtown

Anytown

References

[1]: Massimiliano Cattafi, Marco Gavanelli, Maddalena Nonato, Stefano Alvisi, and Marco Franchini. Optimal placement of valves in a water distribution network with CLP(FD). Theory and Practice of Logic Programming, 11(4-5):731-747, 2011.
[2]: Marco Gavanelli, Maddalena Nonato, and Andrea Peano. An ASP approach for the valves positioning optimization in a water distribution system. Journal of Logic and Computation. Accepted for publication.
[3]: Marco Gavanelli, Maddalena Nonato, Andrea Peano, Stefano Alvisi, and Marco Franchini. An ASP approach for the valves positioning optimization in a water distribution system. In Francesca Lisi, editor, 9th Italian Convention on Computational Logic (CILC 2012), Rome, Italy, volume 857 of CEUR workshop proceedings, pages 134-148, 2012.
[4]: Orazio Giustolisi and Dragan A. Savic. Identification of segments and optimal isolation valve system design in water distribution networks. Urban Water J., 7(1):1-15, 2010.
[5]: Andrea Peano, Maddalena Nonato, Marco Gavanelli, Stefano Alvisi, and Marco Franchini. A Bilevel Mixed Integer Linear Programming Model for Valves Location in Water Distribution Systems. In Stefan Ravizza and Penny 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.

Personal tools