# 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].

## Predicates

**Input**:`junction/1, pipe/2, dem/3, tank/1, valves_number/1, valves_per_pipe/1`**Output**:`valve/2`

## 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`.

## Example(s)

A possible input is:

valves_number(4). valves_per_pipe(1). junction(1). junction(2). junction(3). junction(4). junction(5). tank(1). 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

## Author(s)

- Author: Andrea Peano
- Affiliation: EnDiF, Universita degli Studi di Ferrara, Italy

## References

[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.