welcome: please sign in
location: FinalProblemDescriptions / ValvesLocation

Valves Location Problem

Problem Description

The Valves Location problem is a typical design issue of Urban Hydraulic Networks. A generic Urban Hydraulic Network can be modelled as an indirect and weighted graph: the nodes represent the junctions of the pipes (junction/1), and the edges represent the pipes. The two arguments of predicate pipe/2 are the two junctions connected by the pipe. The third argument of dem/3 is the weight associated to the pipe defined by the first two arguments, and represents the water demand delivered by the pipe (i.e., the average water demand, in litres/seconds, of the houses that take water from that pipe). One or more tanks feed the network; the tanks are located on the junction nodes given by predicate tank/1.

In order to permit the maintenance of any pipe, each pipe must be isolable. The isolation of a pipe can be performed by closing a set of "isolation valves". In any solution, for every pipe there must exist a set of valves that, when closed, disconnects that pipe from all the tanks.

Valves can only be located on the pipes near one extreme (i.e., near a junction), thus in general there can be at most two valves in a pipe. However, in some instances, the number of valves per pipe can be at most 1. The maximum number of valves in a pipe is given by predicate valves_per_pipe/1 (as said, it can be either 1 or 2).

Due to the limited number of available valves, when a pipe is isolated for maintenance, other pipes become isolated as well: all those pipes that are no longer reachable from one of the tanks. This gives a disruption in the service of water delivery. The measure of disruption (given some isolation) is the total amount of water that is not delivered, given as the sum of the weights on the edges that are unreachable from all tanks. The general measure of disruption is the disruption in the worst case, and the aim is to minimize such a quantity.

A longer description of the problem can be found in [1].


Input format

See Problem Description.

Output format

The output predicate valve/2 states where a valve is placed; e.g., valve(A,B) means that the valve is installed on pipe(A,B) close to the extreme A, while valve(B,A) means that the installation place is on the same pipe, but close to junction B. The total number of available valves is limited, due to the involved costs; the maximum number of valves to be placed in the network is given by predicate valves_number/1.


A possible input is:


junction(1). junction(2). junction(3).
junction(4). junction(5).

pipe(1, 2). pipe(1, 4). pipe(2, 3). 
pipe(2, 4). pipe(3, 4). pipe(3, 5).

dem(1, 2, 57). dem(1, 4, 65). dem(2, 3, 155). 
dem(2, 4, 129). dem(3, 4, 78). dem(3, 5, 200).

The instance consists of 5 pipes and 1 tank (linked to the junction 1). The available valves are 4, and only 1 valve per pipe is allowed. One or more possible valves placements exist for this instance.

Additional sample instances: download

Problem Peculiarities

Type: Optimization Competition: Both

Notes and Updates



[1] M. Cattafi, M. Gavanelli, M. Nonato, S. Alvisi, and M. 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.

ASP Competition 2013: FinalProblemDescriptions/ValvesLocation (last edited 2012-11-20 10:08:33 by PatrikSchneider)