## Description

1. Water distribution networks, as the name suggests transport water from a source (or multiple

sources) and deliver them to demand points. Generally speaking, pressure drives flow, i.e., the

upstream pressure is greater than the downstream pressure. Water can also flow aided by gravity,

i.e., water flows from a higher level to a lower level.

Thus, a difference in elevation and/or pressure provides the driving force for flow. The two are often combined into a single quantity called the

”head”, (expressed in meters) If water flows from point A to point B, the head at point A, HA is greater

than the head at point B, HB.

If the flow rate of water Q is known, the head loss ∆H = HA − HB is

related to the flow rate, diameter and length of the pipe through the following correlation:

HA − HB = ∆H = 4.457 × 108LQ1.85

D4.87 , (1)

where Q is the flow rate in m3/min, HA, HB, ∆H are the heads in meters, L is the length of pipe in

meter, D is the inner diameter of the pipe in mm.

A networks consists of a source node (or multiple sources) and demand points or nodes. The

topography of the network (i.e., where the source is situated, where the demand points are located

etc.), the interconnections between the nodes is usually decided beforehand. The water demand

at the individual demand points is also known.

The task at hand is to decide the diameters of the

pipes used to transport the water. There are two competing factors that have to be traded off when

deciding the optimum pipe diameters: the capital cost of the pipe and pump operating costs. In the

following problems we consider flow by gravity and hence, pump operating costs are zero. A large

diameter pipe would result in a high capital cost, but low head loss. Likewise, a smaller diameter

pipe would result in small capital cost, high head loss.

As expected, one aims to minimize the total

cost. Constraints to be enforced are the demand flow rates at the demand points. In addition, it

is common to specify a minimum head at the demand nodes. The task at hand is to decide the

individual pipe diameters that minimize the total cost while satisfying the constraints.

(a) Consider the network shown in Figure 1. (Refer Fig. 1)

The water distribution network consists of a source node 0 and three demand nodes 1,2 and 3.

Node 0 and node 1 are connected by link I. Likewise, link II connects nodes 1 and 2. Link III

connects nodes 1 and 3. The diameters of the pipes are D1, D2, D3 respectively (in mm). Flow

is by gravity and it is possible to achieve a head of 100 m at source node 0. Minimum head

values at nodes 1, 2 and 3 are 80, 85 and 80 m respectively. Lengths of links I, II and III

1

Figure 1

0

3

2

0 1

I

II

III Figure 1: Water distribution network

are 300, 500 and 400 m respectively. Flow rates in links I, II and III are 9,3 and 2 m3/min

respectively. The cost of the pipe per unit length (in Rs.) can be estimated by the correlation:

c = 1.2654D1.327

, (2)

where D is the diameter of the pipe. Since flow is by gravity, there are no operating costs

associated with this network, i.e., total cost is simply the sum of capital costs of the pipes. The

task at hand is to decide the diameters of the pipes, D1, D2, D3 respectively.

(b) Write down expressions for the heads at nodes 1, 2 and 3 in terms of D1, D2, D3. Hint: Head

loss across pipes connected in series is equal to sum of individual head losses.

(c) Write down expression for the total cost, i.e., sum of costs of links I, II and III.

(d) Formulate the appropriate optimization problem to minimize the costs while ensuring that the

heads at nodes 1, 2 and 3 are greater than the minimum values.

(e) At the optimum, what do you expect the values of the head at nodes 1, 2 and 3 to be? Give

reasons.

(f) Unlike previously, we will consider the heads at nodes 1,2 and 3, viz., H1, H2, H3 to be the

decision variables.

(g) Reformulate the problem to minimize pipe cost subject to the minimum head requirements at

1, 2 and 3 in terms of H1, H2 and H3.

(h) Reduce this formulation to an equality constrained problem.

(i) The optimization formulation that you derived in Question has two issues: The first is that it is

a nonlinear constrained optimization problem. We have not yet discussed solution techniques

for the same in class. Fortunately for you, I will provide the optimal solution: D1 = 303.5,

D2 = 209.3 and D3 = 155.8, all in mm.

The second issue is that these are odd sizes, i.e.,

commercially available pipes are available only in certain diameters, e.g., 80 mm, 100mm, 125

mm etc. Table 1 contains a list of the commercially available pipes and their unit costs. Clearly,

pipes with diameters 303.5 mm, 209.3 mm and 155.8 mm are not available commercially. One

solution to avoid this is to restrict the solution space to pipes from the discrete set.

However,

this can lead to a combinatorially difficult problem. In this example, this would mean examining

potentially 143 combinations. Another solution is to simply ”round” off the pipe diameter to the

next commercially available pipe size.

A more sophisticated approach is to use 2 closest available pipe sizes in series, i.e., we replace the odd size by two pipes having adjacent diameters

and connect them in series. One of the pipes has diameter larger and the other smaller than

2

Table 1: Commercially available pipe diameters

Sr no Pipe dia (mm) Unit costs (Rs./m)

1 80 424

2 100 570

3 125 767

4 150 977

5 200 1431

6 250 1924

7 300 2451

8 350 3008

9 400 3591

10 450 4198

11 500 4828

12 600 6149

13 700 7545

14 750 8269

the odd diameter. E.g., the pipe of diameter 303.5 mm is replaced by two pipes of diameter

300 mm and 350 mm, such that the total length is still 300 m. If L

I

1 and L

I

2 are the lengths

of the pipe having 300 and 350 mm diameter respectively, we have that L

I

1 + L

I

2 = 300.

The

advantage of this approach is that it results in lower cost than going in for a single pipe of a

commercially available size. Similarly replace link II with pipes of lengths L

II

1

(200 mm dia)

and L

II

1

(250 mm dia) respectively. Repeat for link III with pipes of diameter 150 and 200 mm

diameters.

(j) Rewrite the expression for the cost in terms of the new variables L

I

1

, L

I

2

,L

II

1

, L

II

2

, L

III

1

, L

III

2

.

(k) Neglecting the head loss in the joints, rewrite the expression for the heads in terms of the new

variables.

(l) Reformulate the optimization problem to minimize the total cost in terms of the new decision

variables, while meeting the minimum head requirements.

(m) Show that it is a Linear Program and express it in the form:

min c

0x,s.t. Ax ≤ b, Aeqx = beq, x ≥ 0.

Write out the variable x and the matrices and vectors clearly.

2. We will now consider a larger pipe network shown in Figure 2.

The network consists of source node 0 and 5 demand nodes 1,2,3,4,5. The flow in links I, II,

III, IV and V are 8.5, 5.8, 1.2, 1.6 and 1.3 m3/min respectively. The minimum heads required at

nodes 1,2,3,4 and 5 are 90,85,80,80 and 80 m respectively. The lengths of links I, II, III, IV and

V are 1000, 600, 400, 300 and 300 m respectively. The head available at node 0 is 115 m.

(a) Repeat parts (1d), (1g) making appropriate changes.

(b) Solution of the nonlinear optimization results in pipes of 304.9, 267.5, 151.9, 159.8 and 119.8

mm diameter respectively. As before, replace the odd pipe by using adjacent pipe diameters,

formulate the optimization problem as in (1m).

3

0

1 2 3

5 4

I II III

IV V

Figure 2: Water distribution network 2

3. In both networks, we agreed to replace an odd size pipe by a combination of 2 adjacent pipe

sizes. In this exercise, you will allow any link to be composed of a series combination of all of the

14 commercially available pipe sizes, i.e., if there is a link of length 300 m, we will allow it to be

replaced by L

I

1 of diameter 80 mm, L

II

1 of diameter 100 mm, . . . LI

14 of diameter 750 mm.

This

problem continues to a be a LP, but with a much higher dimensionality, viz., 14 × 3 = 42 variables

and 14×5 respectively. Will you get the same solution as what you got by replacing the odd diameter

pipe by adjacent diameter pipes? Discuss.

4. I cannot claim that I have all the answers, so I am looking to see how you approach the problem. If you

can help me answer them, all the better! Discussion encouraged In general, how many segments do you

expect the final solution to consist of? 1,2,3 all 14? Can you prove it? Will they be adjacent? If

so, what additional conditions must be imposed?

I can extend this idea to a pipe of continuously

varying diameters by considering allowing pipes having incrementally increasing diameters, i.e.,

given a diameter range [d1, d2, divide into N equi-spaced intervals of size ∆. So, I have pipes

of diameters d1, d1 + ∆, d1 + 2∆, . . . , dN = d2. Let l1, l2, . . . , lN be corresponding lengths of pipe.

If in the earlier question, you were able to prove that the final solution will consist of only k pipe

sizes, you can extend this idea here to show that even allowing for continuously varying diameters,

the final solution consists of only finite set of diameters.

You may find the following materials and

references therein useful:

Optimal design of water distribution networks by P R Bhave. (One copy supposedly available in

library.)

“Two Adjacent Pipe Diameters at the Optimal Solution in the Water Distribution Network Models”,

Fujiwara and Dey, Water Resources Research, 23(8), 1457 − 1460, 1987.

5. Formulate the coin changing problem as an optimization problem.

6. Given an infinite supply of coins of denomination 2

0

, 2

1

, 2

2

, 2

3

, . . ., prove that the greedy algorithm

will solve the coin changing problem exactly.

7. Determine a set of available coin denominations and an amount such that the greedy algorithm

does not work.

8. You are given n different solid items denoted by x1, x2, . . . , xn each of weight wi and value vi

. You

are a door-to-door salesman and have to pack some or all of these items in a bag. You can carry

a maximum weight W. Obviously, you want to maximize the value. Formulate an optimization

problem to achieve this. What is the nature of this optimization problem?

9. This is similar to the previous problem except that you have multiple copies of each item, C1, C2, . . . , Cn.

i.e., the number of copies of item x1 is C1, and so on. Formulate an optimization problem to maximize the value subject to the maximum weight capacity and the availability of each item. What is

the nature of this optimization problem?

10. This is similar to the previous problem except that you have large number of copies (practically infinite) of each item, Formulate an optimization problem to maximize the value subject to the maximum

weight capacity. What is the nature of this optimization problem?

11. Again, similar to the previous problem, except that the items are liquids and you can carry fractional

amounts. The value of each item is obviously proportional to the volume of each item and this

proportionality constant is the values per unit volume, i.e., ρ1, ρ2, . . . , ρn. Formulate an optimization

problem that maximizes the value of the liquids carried subject to overall volume being smaller than

V . Is there an efficient algorithm to solve this?

12. Consider the following inequality constrained quadratic program

min f(x) = (x1 − 4)2 + (x2 − 5)2

,

subject to

2×2 − 4 − x1 ≤ 0, (3)

x1 + x2 − 5 ≤ 0, (4)

x1 ≤ 3, (5)

−x2 ≤ 0, (6)

−x1 ≤ 0. (7)

Interpret the problem geometrically and determine the solution based on geometry. Sketch the

feasible set.