Design and Optimization of Branched Piped Water Networks

Design and Optimization of
Branched Piped Water Networks
Submitted in partial fulfillment of the requirements of the degree of

Doctor of Philosophy
submitted by
Nikhil Hooda
(Roll no: 114050009)
Under the Supervision of

Prof. Om P. Damani
Department of Computer Science and Engineering

Indian Institute of Technology Bombay, Mumbai 400076
2019
To my parents
Surender and Rachna Hooda
Abstract
Government bodies responsible for drinking water distribution in developing countries

face the challenging task of designing schemes that provide a quality of service that is
adequate to meet the needs of the citizens at a cost below the strict government norms.
Engineers at these government bodies must undertake the design process using tools that
are not optimal and consider only pipe diameter selection, which is only one component
of the entire scheme design. As such, much of the design process is undertaken in an
ad-hoc and heuristic manner, relying on the experience and intuition of the engineers.
The problem of the capital cost optimization of branched piped networks consists
of choosing pipe diameters for each pipe in the network from a discrete set of commercially
available pipe diameters. Each pipe in the network can consist of multiple segments of
differing diameters. Water networks also consist of intermediate tanks also known as
Elevated Storage Reservoirs (ESRs). These act as buffers between incoming flow from
the primary source and the outgoing flow to the demand nodes. The network from the
primary source to the ESRs is called the primary network, and the network from the
ESRs to the demand nodes is called the secondary network. During the design stage,
the primary and secondary networks are optimized separately, with the ESRs acting as
demand nodes for the primary network. Typically the choice of ESRs locations, their
elevations, and the set of demand nodes to be served by different tanks is manually made
in an ad-hoc fashion before any optimization is done. It is desirable therefore to include
this ESRs configuration choice in the cost optimization process itself. Valves and pumps
help control the water head in the network. The introduction of pumps also introduces
operational cost to the objective function. Particular care must be taken since continuous
high operational costs increases the chance of scheme failure.
Current tools used by the government consider only pipe diameter selection and
provided non optimal designs. Other network components like ESRs, pumps and valves
are designed manually and iteratively, resulting in a final design that is also non optimal.
We present and implement a formulation that solves the problem of pipe diameter selection
optimally. The solution provided is general i.e. each link can consist of any number of
discrete pipe diameters. We extend the formulation to look at multiple components of
a piped water network. In particular, the formulation captures the specific two stage
design approach of rural networks in developing countries, with a partition of the network
into primary and secondary networks. This allows the pipes, ESRs, pumps and valves
vii
of the entire network to be optimized simultaneously instead of the manual iterative
process of design and simulation employed today. Multiple refinements are done to the
formulation to significantly improve performance. We prove that these improvements
result in tighter models, i.e. the set of points of linear relaxation is strictly smaller than
the linear relaxation for the initial model. The resulting model is guaranteed to be optimal
and solves networks of real world importance in a matter of minutes.
The model has been implemented in JalTantra system which is free to use and
publicly available at https://www.cse.iitb.ac.in/jaltantra/. Thus practitioners now have
access to optimization and design system that is free and optimal and considers not just
pipes but also tanks, pumps and valves. JalTantra includes usability features such as
handling multiple file formats and has GIS functionality integrated for ease of providing
network details. Maharashtra Jeevan Pradhikaran (MJP), the government body respon-
sible for the planning, designing, and implementation of water supply schemes for the
state of Maharashtra in India, has officially adopted it as one of the software packages
to be used in the design of water supply schemes. Maharashtra Environmental Engineer-
ing Training and Research Academy (MEETRA), which is responsible for the training
of MJP engineers, has integrated JalTantra into its curriculum. Details of the JalTantra
system has been included in a compendium titled ”Improving the performance of rural
water supply and sanitation sector in Maharashtra”.
Keywords: Water Distribution; Optimization; Integer Linear Program; Pipe Diameter

Selection; Tank Configuration Selection; Pumps and Valves Selection
viii
Contents
Abstract vii
Contents ix
List of Figures xiii
List of Tables xiv
List of Abbreviations xvi
1 Introduction 1
1.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Literature Review 9
2.1 Branched Network Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Linear Programming Techniques . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Non Linear Programming Techniques . . . . . . . . . . . . . . . . . 10
2.2 Looped Network Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Deterministic Techniques . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Metaheuristic Techniques . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Related Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Reliability Considerations . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Network Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Network Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Components of a Rural Piped Water Scheme 17

3.1 Water Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Water Treatment Plant (WTP) . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Mass Balancing Reservoir (MBR) . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Elevated Storage Reservoirs (ESRs) . . . . . . . . . . . . . . . . . . . . . . 18
3.5 Pipes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
ix
3.6 Pumps/Valves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Pipe Diameter Optimization 21

4.1 OnePipe Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1.1 The Objective Function . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1.2 Pipe Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.3 Node Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 TwoPipe Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.2 Pipe Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.3 Node Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.4 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 General Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.2 Pipe Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3.3 Node Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Parallel Pipes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4.2 Pipe Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4.3 Node Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 ESR Sizing and Allocation 31

5.1 The ESR configuration problem . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 ESR Capital Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3 The Push and Pull of Pipes and ESRs on the Total Capital Cost . . . . . . 33
5.4 Model Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.4.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.4.2 Objective Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.4.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6 Pumps/Valves Integration 39
6.1 Model Extension to Include Pumps . . . . . . . . . . . . . . . . . . . . . . 39
6.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.1.2 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.1.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
x
6.2 Model Extension to Include Valves . . . . . . . . . . . . . . . . . . . . . . 42
7 Model Improvements 43
7.1 Pipe Headloss Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.1.1 Initial Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.1.2 Improved Model (Model-2) . . . . . . . . . . . . . . . . . . . . . . 45
7.2 ESR Cost Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.2.1 Initial Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.3 ESR Configuration Improvement . . . . . . . . . . . . . . . . . . . . . . . 62
7.3.1 Initial Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.4 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8 Edge Based Model 75

8.1 Model Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 Tightness Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.3 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
9 JalTantra System Description 81

9.1 First Iteration: A Desktop JAVA Application . . . . . . . . . . . . . . . . 81
9.2 JalTantra 2.0: A Web System . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.3 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.4 Data Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.5 GIS Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
10 Conclusion and Future Work 87

10.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
10.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Appendices 89
I Complete ILP Model 89

I.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
I.2 Model Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
II JalTantra Usage Details 97
III Karegaon Scheme Redesign 105

III.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
xi
III.2 CTARA Proposal for Redesign of Karegaon Scheme . . . . . . . . . . . . . 105
III.3 Scheme Design Process and Design Options . . . . . . . . . . . . . . . . . 106
III.3.1 Source Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
III.3.2 Population and Demand Forecast . . . . . . . . . . . . . . . . . . . 106
III.3.3 WTP and MBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
III.3.4 Pumping Machinery and Rising Main . . . . . . . . . . . . . . . . . 108
III.3.5 ESRs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
III.3.6 Primary Distribution Network . . . . . . . . . . . . . . . . . . . . . 110
III.3.7 Verification of Network using EPANET . . . . . . . . . . . . . . . . 112
III.3.8 Capital Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
References 115
List Of Publications 123
Acknowledgements 125
xii
List of Figures
1.1 Vicious Cycle Leading to Scheme Failure. . . . . . . . . . . . . . . . . . . . 2

3.1 Components of a typical Rural Piped Water Scheme. . . . . . . . . . . . . 17
5.1 Alternate ESR configurations for a sample network. . . . . . . . . . . . . . 31
5.2 Change in downstream head due to introduction of ESR. . . . . . . . . . . 38
7.1 Tightening linear relaxation by introducing constraint. . . . . . . . . . . . 43
7.2 Graph of the cost of a ESR vs its capacity. . . . . . . . . . . . . . . . . . . 50
9.1 General Tab of JalTantra desktop Java application . . . . . . . . . . . . . 81
9.2 Results Tab of JalTantra desktop Java application . . . . . . . . . . . . . . 82
9.3 JalTantra Web System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.4 JalTantra System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.5 EPANET for Mokhada Network . . . . . . . . . . . . . . . . . . . . . . . . 85
9.6 GIS Tool in JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
II.1 General Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
II.2 Nodes Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
II.3 Pipes Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
II.4 Commercial Pipes Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . 100
II.5 ESR Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
II.6 ESR cost Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
II.7 Pump Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
II.8 Node Results Tab of JalTantra . . . . . . . . . . . . . . . . . . . . . . . . . 103
III.1 Tanker Fed Villages in Mokhada Taluka . . . . . . . . . . . . . . . . . . . 106
III.2 Network Layout of the Mokhada Scheme . . . . . . . . . . . . . . . . . . . 110
III.3 EPANET model of the Mokhada Scheme Network . . . . . . . . . . . . . . 112
III.4 Water Heads at various nodes over time in the Mokhada Scheme . . . . . . 113
xiii
List of Tables
2.1 Comparison of performance of various approaches on the two loop network 13

4.1 Size comparison of TwoPipe and General models. . . . . . . . . . . . . . . 26
4.2 Comparison of the General model to the OnePipe model and BRANCH. . 27
5.1 Typical ESR Cost Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 Cost breakup of alternative ESR configurations. . . . . . . . . . . . . . . . 38
6.1 Cost breakup of alternative ESR configurations with pumps. . . . . . . . . 42
7.1 Performance of the various models on the eight networks. . . . . . . . . . . 74
8.1 Performance of the edge based model. . . . . . . . . . . . . . . . . . . . . . 78
III.1 Details of the tanker fed villages in Mokhada Taluka . . . . . . . . . . . . 107
III.2 Details of the Elevated Storage Reservoirs in the Mokhada Scheme . . . . . 109
III.3 Details of the Pipe Network in the Mokhada Scheme . . . . . . . . . . . . 111
III.4 Details of the Capital cost of the Mokhada Scheme . . . . . . . . . . . . . 113
xv
List of Abbreviations
CBC COIN-OR Branch and Cut

CTARA Centre for Technology Alternatives for Rural Areas
DMA District Metered Area
ESR Elevated Storage Reservoir
GA Genetic Algorithms
GIS Geographic Information System
GLPK GNU Linear Programming Kit
GRG Generalized Reduced Gradient
ILP Integer Linear Programming
LP Linear Programming
LPG Linear Programming Gradient
MBR Mass Balancing Reservoir
MJP Maharashtra Jeevan Pradhikaran
MEETRA Maharashtra Environmental Engineering Training
and Research Academy
MLD Million litres per day
MVS Multi Village Scheme
NLP Non Linear Programming
SDG Sustainable Development Goals
SA Simulated Annealing
WTP Water Treatment Plant
xvii
Chapter 1
Introduction
Water is one of the most basic needs of human life. Water distribution networks are an
integral infrastructure component for any society. Globally 750 million people still do
not have access to an improved source of drinking water [5]. The problem is more acute
in the rural areas of developing countries and is only going to exacerbate with growing
populations, rising standards of living and increased awareness of the importance of clean
water for health. Access to safe drinking water by 2030 was one of the 17 Sustainable
Development Goals (SDGs) set by the General Assembly of the UN in 2015 [2].
Large scale projects are undertaken by governments to provide water to huge pop-
ulations with a high initial capital cost as well as continuous operational and mainte-
nance costs. These projects consist of several infrastructure components like pipes, tanks,
pumps, valves etc. The designers of these projects need to choose the type, size, loca-
tion and configurations for each of these components. These choices not only impact the
quality of service but also impact the cost of the scheme. These systems are governed
by complex nonlinear hydraulic equations and have to deal with uncertainty from various
sources i.e. short term and long term demand changes, quantity and quality of water
supply and component failures. The ability to pay the water tariff is often limited for
people in rural areas. For large networks, invariably there are regions with worse cov-
erage and a greater risk of failure. Any disruption of service quickly leads to people in
that region unwilling to pay and reverting to previous unsafe local sources for their water
needs. The economic stress added leads to further deterioration of the performance of
the scheme effecting more and more people. This vicious cycle as seen in figure 1.1, leads
to an eventual collapse of the entire scheme. As such given the costs and complexities
involved and the crucial nature of the service being provided, these networks must be
designed with great care.
The piped water networks for rural schemes are typically gravity fed, since reliable
electricity supply is not a given. The most important aspect in the design of these systems
is the choice of pipe diameters from a discrete set of commercially available pipe diameters.
Figure 1.1: Vicious Cycle Leading to Scheme Failure.
In general, each link (connection between two nodes) can consist of several pipe segments
of differing diameters. Larger the pipe diameters, better the service (pressure), but higher
is the capital cost. The branched piped water network cost optimization problem is the
selection of pipe diameters that minimize the system cost while providing the requisite
service (pressure at demand points).
The water network design problem has been studied in various forms for over 50
years [38]. Different mathematical and algorithmic techniques ranging from deterministic
ones like Linear Programming (LP), Non Linear Programming (NLP) etc. to modern
metaheuristic ones like Genetic Algorithms (GA), Simulated Annealing (SA) etc. have
been used over these past five decades. The networks under consideration can have differ-
ent configurations. They can be branched or looped, gravity fed or pumped. Additionally,
different subset of components of the network can be considered. Branched networks are
common in rural areas since the redundancy provided by looped networks is an unafford-
able luxury.
Maharashtra Jeevan Pradhikaran (MJP) is the government body responsible for
the planning, designing and implementation of water supply schemes for the state of
Maharashtra in India. It employs over 1500 engineers and over the past several decades has
designed more than 11,000 rural water supply schemes. MJP when deciding to design and
implement a scheme must adhere to strict government cost guidelines. In 2013, a study
was undertaken by CTARA, IIT Bombay [33] to evaluate the feasibility of augmentation
of the scope of the Karegaon scheme to include a cluster of 13 tanker fed villages in its
neighbourhood. The primary objective of the study was the evaluation of the techno-
2
economic feasibility of a multi village water supply scheme (MVS) to supply drinking
water to the cluster of tanker fed villages in the neighbourhood of Karegaon scheme in
Mokhada Taluka. A step by step process following guidelines and protocols used by
MJP in their design process was used for this purpose. The secondary objective was
to understand the process thoroughly and identify where and how the process could be
improved. Details of the scheme design can be found in Appendix III.
Government bodies in India like the MJP use software like BRANCH, EPANET
and WaterGEMS ([33], [69], [71], [79]) for the design of multi village schemes. BRANCH
and LOOP [53] are optimization tools developed by the World Bank that attempt to min-
imize pipe cost for branched and looped pipe networks respectively. It is the software of
choice for MJP engineers when designing a rural water scheme. Alternatively, some engi-
neers use the commercial software WaterGEMS [4] to design and analyse water networks.
Since it uses genetic algorithms, the cost optimization is heuristic and thus non-optimal.
EPANET [68] is a water network modelling software that performs extended period sim-
ulation of the hydraulics of a water network. It is used to analyse and verify the network
once its components have been designed.
Both BRANCH and WaterGEMS consider only the pipe diameter selection compo-
nent of water network design. Beyond just pipe diameter selection, various other decisions
need to be made regarding the components comprising the scheme design. Most choices
like source selection, ESR distribution, valve location, etc. are made in an ad-hoc manner
rather than optimizing overall. The designer’s intuition and experience are relied on to
make these choices. When using BRANCH for calculating pipe diameters in the design
of Karegaon scheme, we found it has limited capabilities in terms of the number of pipes
(at most 125) and does not guarantee an optimal solution. Despite BRANCH being free
to use, due to difficulty in its usage, many designers even use spreadsheets to manually
choose pipe diameters by a trial and error process.
Given the lack of free and optimal options we decided to develop an open source
system, JalTantra that could not just optimally select pipe diameters but also aid the
design of the other components of a typical water network. We ran several training ses-
sions with government engineers on using JalTantra. Maharashtra Jeevan Pradhikaran
(MJP) has officially adopted it as one of the software packages to be used in the design of
water supply schemes. Maharashtra Environmental Engineering Training and Research
Academy (MEETRA), which is responsible for the training of MJP engineers, has inte-
grated JalTantra into its curriculum. Additionally, details of the JalTantra system has
been included in a compendium titled ”Improving the performance of rural water supply
and sanitation sector in Maharashtra”.
3
1.1 Objective
Our aim, in most general terms, is to help the real world practitioners in the design
and optimization of piped water networks. In this work, we specifically focus on rural
networks in developing countries. Government engineers in charge of designing these
networks currently utilize software that only help design a part of the network and that
too sub-optimally. Other components are designed by trial and error and by relying on
the intuition and experience of the designer. Therefore our specific aim in the current
work is to develop a general formulation that captures several network components and
create a design and optimization system that implements this formulation. Given this
context, here are some of the properties that the system must have:
• It must optimize the location and sizing of multiple network components like pipes,
tanks, pumps and valves.
• The solutions it provides must be optimal, fast and consistent.
• It should be cross-platform, easy to use and be able to take inputs in legacy formats,
so that users can transition to the new system easily. Modern technology like GIS
should be leveraged to ease the design process. It must be extensible so that such
new features can be easily implemented based on user feedback.
1.2 Contributions
Existing software used by government engineers in the design of water networks are non-
optimal and restrict themselves to the optimization of pipe diameters only. Remaining
components are designed by trial and error using the simulation software EPANET. In
this work, we extend the problem and create a formulation that includes tanks, pumps
and valves in addition to pipe diameters. This formulation is fast and optimal and is
implemented in our free to use design and optimization system JalTantra.
In [55], an ILP formulation is proposed for the special case of one pipe diameter
per link. While ILP in general is NP-hard, we found that for network sizes of real world
interest, an optimal solution to the special formulation could be computed in reasonable
time. This means that currently one can either get an optimal solution for the special
case of one piped segment per link [55] or get a non-optimal solution for the general case
of multiple pipe segments per link [53]. We propose a formulation that solves the general
problem while still maintaining optimality. We implement this model into our network
design system called JalTantra.
As part of extending JalTantra beyond just pipe diameter selection, we introduce
other network components into the model. Water networks also consist of intermediate
4
tanks also known as ESRs (Elevated Storage Reservoirs) that act as buffers between
incoming flow from the primary source and the outgoing flow to the demand nodes. The
network from the primary source to the ESRs is called the primary network, and the
network from the ESRs to the demand nodes is called the secondary network. During
the design stage, the primary and secondary networks are optimized separately with the
ESRs acting as demand nodes for the primary network. Typically, the choice of ESR
locations, their elevations, and the set of demand nodes to be served by different ESRs,
is manually made in an ad-hoc fashion before any optimization is done. It is desirable
therefore to include this ESR configuration choice in the cost optimization process itself.
Therefore, we extend our model to an Integer Linear Program (ILP) model that integrates
the same to the standard pipe diameter selection problem. Other components like valves
and pumps are also incorporated into the network model. The inclusion of pumps in
particular is significant since it means that apart from the capital cost, operational cost
also needs to be considered.
The extension to an Integer Linear Program model has a significant impact on the
performance of the model. Large networks whose pipe diameter was selected in a matter of
seconds, need hours for the ESR configuration selection. In order to improve performance,
we refine the model in several iterations. These involve exploring alternative formulations
and tightening existing constraints i.e. reducing the set of points in the linear relaxation
of the set described by the constraints. For each of the refinements, we prove that the
resulting model is a strict improvement over the previous model. This brings down the
time taken to solve even large networks of 200 nodes to a few minutes.
In summary, in this thesis we make the following contributions:
• Existing software, used by government agencies in developing countries, look at

only the pipe diameter selection problem and do so non optimally. Other network
components like ESRs, pumps and valves are designed manually and iteratively,
resulting in a final design that is also non optimal. We first consider the pipe
diameter selection problem and present a formulation that solves the pipe diameter
selection problem optimally. The solution provided is general i.e. each link can
consist of any number of discrete pipe diameters.
• We broaden the problem statement and extend the formulation to consider the other
components of a piped water network i.e. ESRs, pumps and valves. In particular,
the formulation captures the specific two stage design approach of rural networks
in developing countries, with a partition of the network into primary and secondary
networks. This allows the pipes, ESRs, pumps and valves of the entire network to
be optimized simultaneously instead of the manual iterative process of design and
5
simulation employed today.
• Multiple refinements are done to the model by exploring alternative formulations

and tightening existing constraints i.e. reducing the set of points in the linear
relaxation of the set described by the constraints. For each of the refinements, we
prove that the resulting model is a strict improvement over the previous model.
Networks of real world importance can be solved optimally in a matter of minutes.
• We implement these provably optimal and fast formulations in our web based net-
work design system, JalTantra. Thus, we fill an important gap in the real world
design of piped water networks for rural communities in the developing world. This
has led to the adoption of JalTantra by government bodies in the design of such
networks.
1.3 Structure of the Thesis

The thesis is structured as follows:
Chapter 1: Introduction. We introduce the problem of design and optimization
of piped water networks. We motivate the importance of robust design and the difficulty
in achieving it. We conclude the Chapter by stating the objective and the contributions
of the thesis.
Chapter 2: Literature Review. We go over the existing literature on design
of water networks. We discuss various approaches employed over the years for both
branched and looped water networks. We further provide some background on closely
related problems of network reliability, operation and generation.
Chapter 3: Components of a Rural Piped Water Scheme. We describe
the components of a typical rural piped water scheme. We describe how each of the
component contributes to both quality of service provided and the cost of the scheme.
Chapter 4: Pipe Diameter Optimization. We look at various approaches
to the selection of pipe diameters for a water network. The first approach fixes each
link in the network to at most one pipe diameter. We then extend this to at most two
pipe diameters for each link using the result that in the optimal case at most two pipe
diameters would be required. We show how a general LP model outperforms the two
pipe approach in terms of time taken while providing the same final optimal solution. We
also extend the model to include laying of parallel pipes in the case of augmentation of
existing schemes.
Chapter 5: ESR Sizing and Allocation. We describe the ESR configuration
problem for a piped water network and how the introduction of ESRs splits the water
network into primary and secondary networks. We motivate the importance of including
6
ESR configuration into the optimization process due its impact on total capital cost.
We then extend the general LP model for pipe diameter selection to an ILP model that
considers ESR configuration and the resulting constraints that influence the hydraulics in
the system.
Chapter 6: Pumps/Valves Integration. We describe the impact including
pumps and valves has in a water network by increasing/decreasing the pressure head
available in the system. The introduction of pumps in particular extend the cost to not
just the initial capital cost but also an ongoing operational cost that must be considered.
We extend our ILP model to include pumps and valves and modify the objective to the
sum of capital and operational cost.
Chapter 7: Model Improvements. The iterative extension of the model to
include more complicated constraints and objectives led to a deterioration in performance.
In this chapter, we describe three major improvements that were made to tighten the
model. For each, we prove that the linear relaxation of the new constraints is a strict
subset of the linear relaxation of the previous points. We then show practical results of
these improvements by comparing performance over eight water networks.
Chapter 8: Edge Based Model. The ILP model described so far uses node
based variables to capture the partitioning of the network into primary and secondary
networks. In this chapter we briefly look at an alternative edge based model. We show
that the set of constraints that describe valid network configurations using edge based
variables is tight. The performance overall remains worse than the node based approach.
Chapter 9: JalTantra System Description. We describe the JalTantra web
system that implements the model to optimize network components.
Chapter 10: Conclusion and Future Work. We conclude the thesis by sum-
marizing the work done and suggest some future research directions.
Appendix I: Complete ILP Model. We describe the variables, constraints and
the objective of the complete ILP model.
Appendix II: JalTantra Usage Details. We describe details on the various
tabs of the JalTantra system and how to use the system.
Appendix III: Karegaon Scheme Redesign. We provide details of the Kare-
gaon scheme redesign done in 2013, which led to the research work presented in this
thesis.
7
8
Chapter 2
Literature Review
The design of a multi village piped water network involves the choosing the sizing and
location of the various networks components that make up the network. These choices
determine the level of service provided as well as the cost of the network. As early as 1895
[67], networks were being manually designed using the economic velocity principle. Piped
water network cost optimization using computer science techniques has been studied for
more than 50 years now. Various approaches have been employed to different versions of
the network optimization problem. Different versions of the problem involve either looking
at different subsets of the components of the network or making different assumptions
about the network configuration.
2.1 Branched Network Design

The earliest approaches looked at solely the pipe diameter optimization problem. In this
case the demand and the network topology were fixed, and the pipe diameters were the
variables to be determined such that sufficient heads were achieved at each of the nodes
while minimizing the capital cost of the pipes. A piped water network can be branched
or looped i.e. the network links are connected such that there is at least one loop in the
network. Rural networks are typically branched. Such networks are easier to optimize
since conservation of mass equations can be used to determine the flow required in each
pipe of the network. In looped networks however, apart from the pipe diameter, flow is
an additional parameter to be determined.
2.1.1 Linear Programming Techniques
In 1968, Karmeli et al. [38] used a Linear Programming (LP) model for determining pipe
diameters in a branched network. The head loss in a pipe is computed using the Hazen-
Williams equation [74] and the cost of the pipe is assumed to be a linear function of the
length. The choice of diameters for the pipes is made from a discrete set of commercially
available pipe diameters with the unit cost for each diameter known a priori. Since the
network is branched, the flow through each link is known and the headloss per unit
9
length can be pre computed for each of the commercially available pipe diameters. The
above model is extend by Calhoun [11] to include a pump at the source of the network.
Thus the source head becomes an additional parameter to be optimized. The model is
further extended by Robinson and Austin [54] by considering pressure ratings for pipes
and including pressure reducing valves. These inclusions therefore introduce maximum
head constraints in the model. Additionally the cost of source head is now considered to
be nonlinear and therefore the network is designed iteratively by solving a series of LP
models. Although providing optimal solutions, these LP models were found to be too
large for networks with large number of pipes. Bhave [6] presented a heuristic method
which reduced the number of candidate pipe diameters being considered.
2.1.2 Non Linear Programming Techniques
An alternate approach to heuristically reducing the search space was to attempt to obtain
an analytical solution. Mandry [48] considers the cost to be an explicit function of the
diameter, rather than looking up unit cost of discrete diameter sizes. The resultant model
therefore contains non linear terms and Non Linear Programming (NLP) techniques are
used to solve the model. Swamee et al. [65] extend the model to include initial head as a
variable, with both pumping and overhead tank costs considered. The solution provided
by these models however contains continuous pipe diameters instead of the discretely sized
commercially available pipe diameters. For any practical application the suggested pipe
diameters would have to be rounded to discrete diameters, which renders the solution non
optimal. Fujiwara and Dey [23] propose a two step approach using both LP and NLP
formulations. In the first step an NLP formulation similar to the one proposed by Swamee
et al. [65] is used to obtain continuous pipe diameters. These are then used to create a
subset of candidate discrete diameters from all available ones. Then in the second stage
a LP model similar to Karmeli et al. is employed to obtain the optimal solution. These
NLP techniques however make the assumption that the minimum head required at all
end nodes are equal. Additionally, no minimum head requirements are considered for any
internal nodes in the network. Young [78] proposes a NLP approach which can handle
both non equal head requirements and consider internal nodes.
2.2 Looped Network Design

Branched networks are typically used in the case of rural areas. Urban areas however
contain looped networks since they provide additional reliability. In branched networks,
if demands are known, the flow through each pipe in the network is fixed. The com-
plexity introduced by allowing networks to be looped is that the flows in the pipes are
10
now variables. This causes the optimization of looped networks problem to be neces-
sarily nonlinear and nonconvex [20]. Techniques used to solve looped networks, be they
deterministic or metaheuristic, have a common iterative approach. An initial solution is
proposed which is then tested and verified using a hydraulic solver. Then depending on
the output from the hydraulic solver variables are modified to generate a new solution.
These process is iteratively repeated till a predetermined stopping criteria is met. The
difference in the various approaches lies in what components of the network are being
considered and how candidate solutions are modified at each iteration.
2.2.1 Deterministic Techniques
In 1968, Jacoby [34] proposed a non linear integer program to design a looped net-
work. The diameters considered are continuous which are later rounded off to integers.
Watanatada [73] extends the model to include flow rate and minimum head requirement
constraints. Shamir [62] further extends the Watanatada model and considers multiple
demand patterns. These approaches use gradient methods. An initial distribution of flows
and diameters is assumed for the network which satisfy all the constraints. The gradi-
ent is then computed for the objective function. Diameters and flows are moved on the
gradient to give the next set of variables. This process is then repeated till the stopping
criterion is met. Lansey and Mays [40] use a model similar to Shamir [62]. Additionally,
they utilize a network solver for the optimization. The variables are separated into two
sets, dependant(node heads) and independent(diameters and flows). For a given set of
independent variables, the network solver computes the dependant variables using hy-
draulic equations. The optimizer then computes a new set of independent variables using
a Generalized Reduced Gradient (GRG) method and the process is repeated. Alperovtis
and Shamir [1] introduce a Linear Programming Gradient (LPG) method to design looped
networks. Initially a set of fixed values is assumed for the flows in the links. Then a LP
model similar to Karmeli [38] is run to compute the pipe diameters. The flows are then
modified using a gradient method and the process is repeated till the stopping criterion is
met. Fujiwara et al. [25] use a method similar to [1] and improve on the modifying flows
step which results in a faster convergence. Eiger et al. [20] show that any formulation of
the looped network optimization must be nonconvex and nonlinear. They also show that
previous gradient approaches ignore the fact that the gradient of the objective function
need not always exist. Eiger et al. explicitly consider this and propose a nonsmooth
optimization algorithm which provided local optima. The problem is optimized globally
by using branch and bound techniques. Samani and Mottaghi [55] use binary variables
to represent if a particular pipe diameter is used for a link and therefore use an Integer
Linear Program (ILP) to model the problem. The use of binary variables results in a
11
single diameter being suggested for each link.
2.2.2 Metaheuristic Techniques
Most recent work in the design of piped water networks has been in utilizing various meta-
heuristic techniques. These techniques encompass a range of ”meta” level algorithms used
to explore large search spaces in order to find optimal solutions. They are ”meta” level
since they are independent of the specific problem being considered. This is unlike most
heuristic approaches which attempt to exploit some structure unique to the problem
under consideration. Constraints are modelled using penalty functions that are added
to the objective cost function. Fixing the values for the set of variables determines the
objective cost function. The variables are then iteratively modified in several generations
till a stopping criterion is met. The difference in the various techniques lies in how this
iterative modification of variables is done. Meta-heuristic techniques are inspired from
various phenomena observed in the natural world.
The largest subset of these meta heuristic techniques that have been used in the
water network design problem are genetic algorithms (GA). Simpson et al. [63] used GAs
to optimally determine pipe diameters for piped water networks. GA is inspired from
evolution theory. In GA several instances of the decision variables are simultaneously
considered and maintained. Each instance represents an individual in a population. With
each iteration, individuals are modified by reproduction (elements from two individuals
are combined to create a new individual) and mutation (some elements of an individual
are randomly changed). ”Fitness” (objective cost) for the new set of individuals is then
computed. More fit (lower cost) individuals have a higher probability of surviving and be-
ing selected for future reproduction and mutation. Dandy et al. [16] suggest an improved
GA model which uses a modified fitness function and mutation is done only to adjacent
pipe diameters. Montesinos et al. [50] also use a modified GA where in each generation
a fixed number of the population is discarded. Additionally each individual can undergo
at most one mutation. Wu and Simpson [75] use GA to design networks which include
pumps, tanks and valves. They use a separate network solver like in Lansey and Mays
[40]. Babayan et al. [3] extend the GA model to include demand uncertainty.
Various meta heuristic techniques, other than GA, have also been employed to
design piped water networks. These include: Simulated Annealing (Cunha and Sousa
[15]) which is inspired by the annealing process where the cost is allowed to increase
with a certain probability allowing one to escape local optimas; Tabu Search (Cunha and
Riberio [14]) which is inspired by human memory processes and tracks the list of already
explored solutions; Ant colony optimization (Maier et al. [44]) which is inspired by group
behavior of large ant colonies where each ”ant” looks at and optimizes one component of
12
the overall structure; Shuffled Frog Leaping Algorithm (Eusuff and Lansey [21]) which is
inspired by evolution of memes (cultural evolution) among a population of frogs where
individuals can be modified not just by parents (in the case of GAs) but also peers.
With the increase in usage of meta-heuristic techniques, multi objective optimiza-
tion approaches began to be considered. Halhal et al. [32] first applied a multi objective
approach to network design, attempting to maximize network benefit while minimizing
network cost. Mala Jetmarova et al. [47] provide a detailed review of various approaches
to the optimization of water distribution systems.
Over the decades of research on the design of looped networks, several small bench-
mark networks such as Hanoi network [25], New York City tunnels [60] and Two Loop
network [1] have been used to compare performance. The two loop network is a simple
network consisting of 8 links(each of length 1000m), 6 demand nodes and 14 commer-
cially available pipe diameters. We compare the performance of some of the approaches
described above using this network in Table 2.1.
Table 2.1: Comparison of performance of various approaches on the two loop network
Alpervotis and Eiger et al. Savic and Samani and
Shamir (1977) (1994) Walters (1997) Mottaghi (2006)
Length Dia Length Dia Length Dia Length Dia

Pipe
(m) (in.) (m) (in.) (m) (in.) (m) (in.)
1 256 20 1000 18 1000 18 1000 18

744 18 0 0 0
2 996.38 8 238.02 12 1000 10 1000 10
3.62 6 761.98 10 0 0
3 1000 18 1000 16 1000 16 1000 16
0 0 0 0
4 319.38 8 1000 1 1000 4 1000 4
680.62 6 0 0 0
5 1000 16 628.86 16 1000 16 1000 16
0 371.14 14 0 0
6 784.94 12 989.05 10 1000 10 1000 10
215.06 10 10.95 8 0 0
7 1000 6 921.86 10 1000 10 1000 10
0 78.14 8 0 0
8 990.93 6 1000 1 1000 1 1000 1
9.07 4 0 0 0
Cost 497.32 402.35 419 419
13
2.3 Related Problems
Apart from the primary objective of determining network components, there are a range of
problems related to water distribution networks. These range from additional considera-
tions during the design stage like reliability analysis to network operation and maintenance
once the scheme has been implemented.
2.3.1 Reliability Considerations
So far the only objective being optimized is the cost of the scheme. Goulter and Coals
[30] explicitly include reliability in the design of looped networks. Each available pipe
diameter is assumed to have a rate of failure per unit length per year. It is assumed than
any connecting link can satisfy the entire demand of a node. The probability of node
isolation is thus computed by computing the probability of failure of each of its connecting
links. A constraint is added to the model for each node restricting this probability within
acceptable limits. Goulter and Bouchart [29] extend the above model to also model
demand failure i.e. the probability that demand at a node exceeds the design values.
This is combined to the link failure probability and a single reliability metric is considered.
Bouchart and Goulter [10] consider demand not only at nodes but also along the entire
length of the links. Su et al. [64] utilize the approach of using a network solver and
the GRG method proposed in [40] and include pumps, tanks and reliability constraints.
Lansey et al. [41] propose a chance constrained NLP model that considers uncertainties
in demands, required pressure heads and pipe roughness. This model is also solved using
GRG. Xu and Goulter [76] extend the Lansey et al. [41] model to include uncertainty of
pipe failure. Duan et al. [19] further extend the model to consider pump failure.
The above reliability analysis is modelled as a failure of components or under
conditions of demand uncertainty. However, in areas with limited water availability a
common point of failure is the uncertainty in supply. Under normal supply conditions the
hydraulics of the system are demand driven i.e. assuming some demand for various nodes
and assuming that those nodes are being fulfilled. Software like EPANET [68] which are
used to analyse these networks assume demand driven hydraulics. But under low supply
and pressure conditions the flows are limited not by the demands but by the pressure
available in the system. Therefore the network needs to be analysed using pressure driven
hydraulics. Bhave [7] proposed a network analysis method which represents the flow as
function of available pressure. Gupta and Bhave [31] extend this approach to consider
reliability under pressure deficient considerations where reliability is based on a node-
reliability factor, volume-reliability factor, and network reliability factor. Sayyed et al.
[59] use the demand driven analysis of EPANET to simulate a pressure driven regime by
14
adding artificial valves and emitters to each node. Mahmoud et al. [43] extended this
approach and improved the scalability by adding the artificial components to a selected
number of nodes. This selection was determined by first doing a normal demand driven
analysis and only those nodes with negative pressures were modified.
2.3.2 Network Generation
In all the above approaches the network layout was assumed to be fixed and known
before the design stage. In 1983, Bhave and Lam [8] consider the problem of determining
the optimal layout of a network given only the locations of the demand nodes and the
supply points. The problem is modelled as a Steiner tree problem where the objective
is to minimize the total length of the links required to connect all the nodes. Lejano
[42] develops a Integer Linear Programming (ILP) formulation for optimizing network
configuration. The objective to be optimized is empirical and includes the capital cost
of pipes and pumps as well as the cost of serving each customer. Therefore it allows for
selecting a subset of customers to be served instead of serving everybody as is typical.
Despite the numerous approaches to the design of networks, their testing has been
inadequate due to a lack of benchmark networks. They are limited to a few small sized
networks such as Hanoi network [25], New York City tunnels [60] and Two Loop network
[1]. This leads to most metaheuristic techniques overfitting the few instances available.
De Corte and Sorenson [18] have developed a tool, HydroGen that can algorithmically
generate large scale water networks with characteristics resembling those of real life net-
works.
2.3.3 Network Operation
Even after the network has been designed the operation and maintenance of large water
networks remains a complex problem. The operation of these networks broadly encom-
passes two areas. Firstly, pump and valve operation which is used to ensure adequate
supply of water under varying and uncertain demand patterns. In particular optimiza-
tion of pump usage is crucial since it constitutes the largest expenditure in the operation
of water networks [70]. The second aspect is the optimization of water quality in the
network.
As with network design, work on network operation has followed a similar path,
starting with deterministic techniques in the 1970s ([1] , [61], [13]) to metaheuristics ([45],
[51]) after the 1990s. Sankar et al. [56] provide an algorithm that looks at the problem of
optimal pump operation in distressed situations where water supply is insufficient. The
optimization thus has to consider cost but also equitable distribution of water. Mala
15
Jetmarova et al. [46] provide a detailed review of the work done in this field over the past
three decades.
Related to network operation is the problem of network maintenance. Leaks are
common due to the pressured environments and result in massive losses of water [66]. In
order to combat leaks and better manage existing networks, urban networks are increas-
ingly getting partitioned into independent sections called District Metered Areas (DMAs).
This partitioning is achieved by cutting off parts of the network from each other using
valves. Savic and Ferrari [57] propose an automated method to create DMAs for an
existing network and compare the characteristics of candidate solutions.
16
Chapter 3
Components of a Rural Piped Water Scheme
The basic premise of a multi village piped water scheme is that water needs to be trans-
ported from a set of common sources of water to a group of villages. This is achieved by
several components pipes, pumps, reservoirs, treatment plants, valves etc. The choices
made in regard to these components contribute to the cost of the scheme as well as the
quality of the service provided. The aim is to minimize cost while maintaining desired
service quality. We briefly go over the components that comprise a typical scheme and
detail how each impact the scheme cost and quality. The layout of a typical multi village
scheme is depicted in Figure 3.1 below (courtesy: CTARA, IITB).
Water is pumped from the source to the water treatment plant (WTP) by the
raw water rising main. From the WTP it is then pumped to the mass balancing reservoir
(MBR) by the pure water rising main. Then we have the primary network where the water
is distributed from the MBR to several Elevated Storage Reservoirs (ESRs). Then comes
the secondary network where the water goes from the ESRs to the individual hamlets.
Finally, we have the tertiary network where water goes from the hamlets to individual
stand posts/homes.
Figure 3.1: Components of a typical Rural Piped Water Scheme.
17
3.1 Water Source
The water source can be surface water (like lakes, reservoirs, rivers etc.) or ground water.
Several different sources might be available from which one or more sources must be
selected to service the scheme. The choice of source depends on several factors like head
of the source, location in relation to the rest of the network, quality of water available,
amount of water that can be sustainably drawn and reliability in times of stress (summer
months). In the present work we assume there is a single known water source which
provides a constant water head to the network irrespective of the amount of water drawn.
3.2 Water Treatment Plant (WTP)

The water that is drawn from the source needs to be treated at a WTP. WTPs vary in
the kind of treatment that they can provide (i.e. which chemicals are used for treatment)
and their capacity (i.e. amount of water that the WTP can process in a day). The factors
influencing the choice of WTP are the supply of water that the scheme needs to provide,
the quality of source water and the task for which water will be consumed (drinking,
irrigation, etc.). In the present work the design of the WTP component is ignored since
we do not consider water quality. The network is designed post the water treatment with
the MBR effectively acting as the source of water. This is because the choice of type and
size of WTP can be made independent of the network design. The type of WTP depends
on the quality of water available. The size of the WTP depends on the total demand
which is known beforehand.
3.3 Mass Balancing Reservoir (MBR)

Water from the WTP is stored in the MBR and then released into the rest of the network.
Thus, it serves as a buffer in the supply of water to the rest of the network. It acts as an
“effective” source of the network and the water head it provides is a key component in
shaping the rest of the network. The choices to be made in regards to the MBR are its
location, elevation and sizing.
3.4 Elevated Storage Reservoirs (ESRs)

These are the reservoirs that are placed at various points of the network from which water
is delivered to the villages. Water is supplied to these ESRs from the MBR. Each ESR
can serve one or more villages. This depends on the relative location of the villages and
the ESR, as well as the amount of water demanded by the villages and the capacity of
the ESR. An important consideration is the elevation of the ESR as this impacts the
18
choice of pipes in the primary and secondary networks. If the location of the ESR is
at a relatively high elevation, the ESR might be placed on the ground and is termed as
a Ground Storage Reservoir (GSR). In the present work, we assume that if ESRs are
included in the optimization, then each ESR must be served by the source and each
demand point must be served by exactly one ESR.
3.5 Pipes
Pipes are the backbone of the water distribution network. As water flows in the pipe,
there is a loss in the water head along the length of the pipe. This is caused by friction
losses due to the movement of water in the pipe. This headloss depends on factors like
the diameter, length and material of the pipe as well as the amount of water flowing in
the pipe. The choice of pipe therefore depends on all these factors. The headloss in a
pipe is calculated by the Hazen-Williams equation [74]. Also, pipes need to withstand
the water pressure that is applied at all times. The amount of pressure that a pipe can
withstand is represented by its pressure rating. There are several types of pipes available
with varying reliability and pressure ratings [49]. In particular for distribution networks
the following three types are commonly used:
• Reinforced Cement Concrete (RCC): Cheap and available in large diameters (upto
2000mm). However can be subject to corrosion if water is acidic and extremely
heavy, thus difficult to handle.
• Ductile Iron (DI): Costlier than RCC but better corrosion resultant and thus longer
lasting. Also available in large diameters (upto 1000m).
• High Density Polyethylene (HDPE): Costliest of the three options. Light and cor-
rosion resistant. However, requires specialized welding, is easier to break and is not
available in high diameters (upto 630mm).
In the present work we assume, for each pipe diameter there is a single type of pipe
available. This is because the choice of pipe is not restricted to hydraulic considerations
and cost. The choice is also determined by operational concerns like the quality of water
available and the reliability of pipe desired which is outside the scope of the current work.
3.6 Pumps/Valves
Pumps and valves help manipulate the water head in the network. Pumps are required
to supply water where water cannot be supplied naturally i.e. via gravity. The power of
the pump required depends on the amount of water to be pumped as well as the water
19
head that needs to be provided. Pumps are one of the primary sources of operational cost
and as such their usage should be strictly on an as needed basis. In the present work, the
efficiency of a pump is assumed constant irrespective of the flow through the pump. This
makes the pump power a linear function of the head provided and the flow through the
pipe. In practice, the efficiency varies over different water flow and head values, which is
represented by a characteristic pump curve. While determining operational cost only the
cost due to pumps is considered. Operational costs arising due to operation of WTP and
maintenance costs are ignored. This is because these costs are independent of the design
of the rest of the network. At times part of the network has excess water pressure due
to huge elevation differences. Pipes therefore must be chosen which can withstand such
pressures leading to a rise in capital cost. If a lower head can serve for the downstream
network, pressure reducing valves can be employed to reduce the pressure and thus allow
the use of pipes with lower pressure rating.
Additionally, in the present work we make the following assumptions about the
network:
• Typically the demand at a location would be distributed across many households.

We aggregate the demand at a village into a single point. If required, the tertiary
network which distributes the water within a village can be separately designed.
• The demand at each point is known and constant throughout the day. This is known
as steady state analysis. In practice however, once the network has been designed
extended period simulation is required to verify the functioning of the network. Our
system JalTantra outputs the result of the optimization as an EPANET file which
can be used to perform the extended period simulation.
• The network configuration i.e. the links connecting the demand points is fixed,
known and branched i.e. there are no loops in the network. This fixes the flow
through each pipe since the demands are known.
Under these assumptions, we develop our design and optimization model by con-
sidering pipes, tanks and pumps/valves over the next three chapters. We then discuss the
modifications made to the model to improve performance in Chapter 7.
20
Chapter 4
Pipe Diameter Optimization
In this chapter we describe the primary problem of network design, selection of pipe
diameters. We first look at an approach from literature that restricts each link in the
network to at most one pipe diameter. We then extend this model to at most two pipes
per link which is guaranteed to be optimal. We show how a more general model which
allows any number of diameters per link results in a much faster formulation. We conclude
by extending the model to include parallel pipes in the case of augmentation of existing
schemes.
4.1 OnePipe Model

Although in general each link in the network can consist of multiple pipe diameters, the
first formulation that we looked at for our problem was to restrict each link in the network
to a single pipe diameter. [55] has an Integer Linear Programming (ILP) formulation for
the problem where only one pipe diameter is used per link. It uses binary variables to
represent the choice of commercial pipe to be made for each link. Henceforth we use the
term OnePipe model while referring to this formulation.
4.1.1 The Objective Function
The objective function to be minimized is the total cost of the pipes chosen for the links
in the network:
NL
X
O(.) = Li Ci (Di ). (1)
i=1
Where,
O(.): The total pipe cost which is a function of the pipe diameters chosen for each
link
N L: The number of links in the network
21
Di : Pipe diameter for the link i
Li : Length of link i
Ci : Cost/length of link i, a function of the pipe diameter Di
The diameters Di can only be chosen from the set of available commercial pipe
diameters. This restriction is represented via binary variables xij . The modified objective
function is:
NL X
X NP
O(.) = Li Cij (Dij )xij . (2)
i=1 j=1
Where,
N P : Number of commercially available pipe diameters
xij : 1 if link i uses pipe diameter j, else 0
4.1.2 Pipe Constraint
For each link the objective function O(.), has terms for each of the available commercial
pipe diameters j. Since each link is to be installed with only one diameter, it means that
exactly one of the binary variables corresponding to each link must be one. Therefore we
get the following pipe constraint for each link i:
NP
X
xij = 1 , i = 1, . . . , N L. (3)
j=1
4.1.3 Node Constraint
At each node a minimum amount of pressure needs to be maintained. The pressure at

any node is calculated from the headloss in the pipes connecting the node to the reference
node i.e. the source for the network. Therefore the pressure constraint for each node n
is:
X
Pn ≤ HR − En − hli , n = 1, . . . , N N. (4)
i∈Sn
Where,
Pn : The minimum pressure that must be maintained at node n
HR : The head supplied by reference node
En : The elevation of node n
N N : The number of nodes in the network
22
Sn : Set of pipes that connect node n to the reference node R
hli : Headloss in link i. It is modeled as summation over HLij i.e. headloss in link i if
the pipe diameter j is chosen. We use the Hazen-Williams formula [74] for headloss
which is given by:
1.852
F Li
10.68 ∗ Li ∗ Rj
HLij = , i = 1, . . . , N L, j = 1, . . . , N P. (5)
Dj4.87
Where,
F Li : Flow in link i
Rj : Pipe roughness of commercial pipe j
Dj : Diameter of commercial pipe j
As with the objective cost function, we introduce xij to linearize the node constraint
which gives us:
NP
XX
Pn ≤ HR − En − HLij xij , n = 1, . . . , N N. (6)
i∈Sn j=1
Now for a given pair of (i, j) values, HLij is just a constant, so we get a linear constraint
with xij as our variables.
4.2 TwoPipe Model

The previous formulation assumes a single pipe diameter for each link in the network.
But this might not be (and usually is not) the optimal solution. In the most general case,
we can have several pipes of varying diameters for a single link in the network. In [24] it is
shown that in the optimal solution, each link will consist of at most two pipe segments of
adjacent diameters. The above will hold if the commercial pipe cost is a convex function
of a power of its diameter, which is the case in practice. We modify the objective function
to incorporate this knowledge about the optimal solution structure as described below.
To generalize the formulation in order to account for multiple pipes per link we introduce
two new continuous variables for each link: li1 and li2 . The previous binary variable
representing the choice of commercial pipe for each link is now broken into two: xij1 and
23
xij2 . Here li1 / li2 represent the length of the two pipes for link i and xij1 /xij2 represent
the choice of diameters for the two pipes. The modified objective function is:
NL X
X NP
O(.) = li1 Cij1 (Dij1 )xij1 + li2 Cij2 (Dij2 )xij2 . (7)
i=1 j=1
This formulation is not linear since we have terms like li1 xij1 which are a product of two
variables. We linearize this equation by introducing variables zij1 :
zij1 = li1 xij1 , i = 1, . . . , N L, j = 1, . . . , N P. (8)
This nonlinear equality is represented by the following set of linear inequalities:
zij1 ≤ Li xij1 , (9)

zij1 ≤ li1 , (10)
zij1 ≥ li1 − Li (1 − xij1 ) . (11)
This linearization is possible since zij1 is a product of a continuous variable and a

binary variable. A similar set of inequalities will be introduced for zij2 as well. Our new
objective function:
NL X
X NP
O(.) = Cij1 (Dij1 )zij1 + Cij2 (Dij2 )zij2 . (12)
i=1 j=1
As before, the choice of pipe diameter must be made from the available commercial pipe
diameters.
NP
X
xij1 = 1 , i = 1, . . . , N L . (13)
j=1
Similar equalities hold for xij2 . We also have an additional constraint for each link i.
li1 + li2 = Li , i = 1, . . . , N L . (14)
The node constraint for minimum pressure requirement now changes since length of each
pipe segment is no longer a constant. Since headloss is linear in the length of the pipe
(5), the length term can be taken out. The headloss HLi in each link i now becomes:
NP
X
HLi = HLij (xij1 lij1 + xij2 lij2 ) , i = 1, . . . , N L , (15)
j=1
24
1.852
F Li
10.68 ∗ Rj
HLij = , i = 1, . . . , N L, j = 1, . . . , N P . (16)
Dj4.87
Replacing the xij lij terms with zij gives the new node constraint:
NP
XX
Pn ≤ HR − En − HLij (zij1 + zij2 ) , n = 1, . . . , N N . (17)
i∈Sn j=1
4.2.4 Computational Results
On testing the new formulation, the run-time performance is found to be very poor.
Whereas for the OnePipe model a 100 node network can be solved in 1.5 seconds, the
new formulation cannot solve optimally even a 10 node network before getting timed out
at 100 seconds.
The reason for this is the large number of new constraints that are added to the
system. Previously all constraints were linear in the number of nodes. We had only one
constraint for each link and one for each node (for an acyclic network, number of links
is one less than the number of nodes). But now, in order to introduce zij1 and zij2 , we
have introduced six new constraints for each (link, pipe diameter) combination. Thus the
number of constraints goes from O(n) for the OnePipe model to O(n2 ) in the TwoPipe
model.
4.3 General Model
If multiple pipes per link are permitted, at most two pipes of adjacent diameters will be
chosen [24]. In the TwoPipe model this knowledge is explicitly used by modelling each link
to be made up of two segments. We then independently determine the commercial pipe
diameter xij and the length lij for each segment. This introduces O(n2 ) product terms,
each of which need to be linearized causing a blowup in the number of constraints. To
overcome this constraint blowup, we ignore the two pipe segment structure of the original
solution. Each link can consist of multiple pipe segments for each possible commercial
pipe diameter. The length of each segment needs to be determined. No explicit choice is
made regarding which commercial pipe diameter is chosen or not. The commercial pipe
diameter is considered chosen if its segment has non-zero length.
We introduce continuous variables lij and do away with the binary choice variables
xij1 and xij2 . Each link is made up of N P components corresponding to the N P pipe
diameters. lij then represents the length of each of these components.
25
We replace the terms li ∗ xij with lij in our objective cost:

NL X
X NP
O(.) = Cij (Dij )lij . (18)
i=1 j=1
Now the pipe constraint simply reduces to:

NP
X
lij = Li , i = 1, . . . , N L . (19)
j=1
In the node constraint we replace xij ∗ Li with lij :

NP
XX
Pn ≤ HR − En − HLij lij , n = 1, . . . , N N . (20)
i∈Sn j=1
As in the case of OnePipe the number of constraints is linear in the number of nodes and
the performance turns out to be much better. Table 4.1 shows the size of model in terms
of variables and constraints for the two approaches.
Table 4.1: Size comparison of TwoPipe and General models.

TwoPipe Model General Model
Nodes Constraints Variables Constraints Variables
n 6n + 8nm* 2n + 4nm 2n nm
10 860 420 20 200
100 8600 4200 200 2000
*m is the number of commercial pipe diameters which is taken as 10.
For a 100 node network we have around 200 inequalities for the general formulation.
But for the two-pipe model, a network with just 10 nodes the number of constraints is
around 800! Also by eliminating binary variables and replacing them with continuous
variables we have converted what is an Integer Linear Program (ILP) to a Linear Program
(LP). While ILPs are NP hard [52], LPs can be solved in Polynomial time [39]. This is
very significant since we are able to solve the LP formulation of a 1000 node network in
two seconds even though it contains 2000 constraints.
26
We now have a more general formulation for our pipe diameter optimization prob-
lem. We have the added benefit of not restricting the solution to two pipes per link. If the
necessary convexity conditions [24] are met, our solution should naturally contain only
two pipes per link with adjacent diameters.
We evaluate the performance of the general approach in comparison to the OnePipe
model and the popular design software BRANCH. Table 4.2 presents the performance in
terms of objective cost as well as running time of the three methods over six test net-
works. For the Gen100 network, BRANCH terminated with a memory overflow message.
Since the stated maximum number of nodes is 125, the Gen1000 network is not run on
BRANCH.
The time taken by both the OnePipe model and the general model is less than half
a second for the first four networks. But the ILP vs. LP nature is borne out for the two
larger networks. In fact, for the Gen1000 the OnePipe model also gets timed out.
Being optimal, the general model indeed outperforms both BRANCH and the
OnePipe model for all six networks in terms of objective cost. Both BRANCH and
our proposed model use a more general formulation and hence better cost results are
to be expected. The general model performs better than BRANCH since we use a LP
formulation that is solved optimally whereas BRANCH uses a heuristic approach. In fact,
for two of the first four networks even the OnePipe model performs better than BRANCH.
Table 4.2: Comparison of the General model to the OnePipe model and BRANCH.
BRANCH OnePipe Model General Model
Number Cost Time Cost Time Cost Time
Network
of Nodes (1000 Rs) (msec) (1000 Rs) (msec) (1000 Rs) (msec)
Mokhada 37 24,652 119380 24,317 429 24,181 387

Shahpur 21 29,082 34878 29,523 356 28,895 318
Khardi 11 21,281 4207 21,267 256 21,184 247
Gen5 5 1958 1105 2020 243 1949 228
Gen100 100 - - 93,718 1531 90,512 628
Gen1000 1000 - - 5,80,578 Timeout 5,62,564 2023
4.4 Parallel Pipes

A common design challenge is the augmentation of existing networks. The previous
infrastructure is frequently of not sufficient capacity since it was designed for a smaller
population. As part of the previous model, a user could provide diameters for existing
pipes in the network. Therefore, some links in the model could have fixed diameters. It
27
is possible for this network configuration, that all constraints cannot be met, especially if
the fixed diameters provided are very small.
It is therefore desirable to allow pipes to be placed in parallel to existing pipes
to augment capacity if and when required. To capture this requirement we introduce
binary variables pij and pi for each link i and commercial pipe diameter j. pij represents
the choice of diameter for the parallel pipe for link i. No parallel pipe being chosen is
represented by the variable pi . Note that since we are introducing binary variables our
program now once again reverts to an Integer Linear Program. But in this particular case
the performance is not affected significantly since these variables are introduced only in the
case of links with existing pipes, and then too only if user permits the addition of parallel
pipes to those links. These are typically going to be a very small number as compared to
the total links in the network. The modified objective function and constraints are given
below.
Let SE be the set of links which have existing pipes and S∼E the set of remaining links.
Note that existing links don’t contribute to the cost. Then the modified objective function
is:
X NP
NL X NL X
X NP
O(.) = Cij (Dij )lij + Li Cij (Dij )pij . (21)
i∈S∼E j=1 i∈SE j=1
For all links that have existing pipes we add an additional pipe constraint:
NP
X
pi + pij = 1 , i = 1, . . . , N L . (22)
j=1
For links with existing pipes, headloss changes since the flow in those pipes now depends
on the parallel pipe chosen:
NP
XX
0
Pn ≤ HR − En − HLij lij , n = 1, . . . , N N , (23)
i∈Sn j=1
1.852
F Lij
10.68 ∗ Rj
HLij = , i = 1, . . . , N L, j = 1, . . . , N P , (24)
Dj4.87
0
lij = lij , i ∈ S∼E , (25)
0
lij = Li ∗ pij , i ∈ SE , (26)
28
F Lij = F Li , i ∈ S∼E , (27)
4.87 !−1
Rj Dj 1.852
F Lij = F Li 1+ ∗ , i ∈ SE . (28)
Ri Di
Where Ri and Di are the roughness and pipe diameter values of the existing pipe.
In this chapter, we discussed the core problem of network design, the selection of
pipe diameters from a discrete set of commercially available pipe diameters and looked at
several approaches to solve the problem. Software in use by government engineers today,
restrict themselves to this problem. But networks consist of several other components
as well which impact the cost of the network and level of service provided. In the next
chapter we discuss tanks/ESRs, why they are important to the cost of the network and
how we integrated them into our general model.
29
30
Chapter 5
ESR Sizing and Allocation
5.1 The ESR configuration problem

The ESR/Tank configuration problem is to determine the ESR locations, heights, ca-
pacities, and the downstream demand nodes that each ESR will service. The purpose
of using ESRs is to divide the network into a primary network and secondary networks.
Primary network distributes the water from the source to the ESRs. Each ESR then
distributes water to the demand nodes it is responsible for. This division of responsibility
helps in providing a more equitable distribution of water in the entire network. Typically
this choice of ESR configuration is made in an ad-hoc manner, relying on the intuition
and experience of the designer. This choice is integrated in our capital cost optimization
formulation and the same is implemented in JalTantra.
Figure 5.1: Alternate ESR configurations for a sample network.
ESR allocation in a network can be done in several ways. The choice can be an ESR
for each demand node or a single ESR for the entire network or any other configuration in
31
between these two extremes. This allocation then determines the ESR capacity. Figure 5.1
depicts the two extreme configurations as well as the “optimal” one for a sample network
with six demand nodes. Note how the choice affects the primary/secondary networks.
5.2 ESR Capital Cost
In Chapter 4 we discussed the capital cost of pipes which is the first source of network
capital cost. The second component of network cost is the cost of the ESRs.The capital
cost for ESRs depends on the size of the ESRs to be built. However note that the cost
of a ESR rises sub-linearly. That is, doubling the ESR capacity changes the cost to less
than double the original cost. The non-linear ESR cost is a piece-wise linear function,
represented by a table which divides the ESR capacity into several brackets. A typical
ESR cost table from [49] is shown in table 5.1. An ESR with a capacity of 55000 litres
will therefore cost 935800 + 9.64 * (55000 - 50000) = 984000 Rs.
Table 5.1: Typical ESR Cost Table.

Minimum Maximum Base Cost Unit Cost
Capacity (l) Capacity (l) (Rs) (Rs)
0 25000 0 24.47
25000 50000 611800 12.96
50000 75000 935800 9.64
75000 100000 1178800 8.64
100000 150000 1394800 7.23
150000 200000 1772800 6.03
200000 250000 2096800 5.4
250000 300000 2366800 5.4
300000 400000 2636800 5.12
400000 500000 3176800 4.32
500000 750000 3608800 4.32
750000 1000000 4688000 4.32
1000000 1500000 5768800 4.32
1500000 2000000 7928800 3.92
2000000 - 9548800 3.24
32
5.3 The Push and Pull of Pipes and ESRs on the Total Capital
Cost
The distribution of headloss in the network dictates if the node pressure requirements are
being satisfied or not. Headloss in a pipe depends on the length and diameter of the pipe
used, as well as the flow through the pipe. For the branched networks, the flow in a pipe
depends on whether the pipe is part of a primary network, or a secondary network, which
in turn depends on the choice of ESR configurations. Typically the primary network runs
for the entire day whereas secondary networks are scheduled to run for a few hours every
day in order to manage the distribution of water. Thus flow rate in a secondary network
is higher than that in a primary network. Therefore, for the same headloss across a pipe,
higher diameters are required in case of a secondary network. This means that the total
pipe cost is minimized when the entire network is a primary network, that is, there is a
ESR installed at each demand node, and there are no secondary networks (for e.g. in the
second configuration shown in Figure 5.1).
The total ESR capacity required for the network is same regardless of the ESR
configuration, that is, the number, locations, and the allocation of demand nodes to the
ESRs. The cost for various configurations, however, would be different, since as mentioned
earlier, individual ESR cost rises sublinearly with its capacity. Therefore the total ESR
cost is minimized when a single ESR serves the entire network (for e.g. in the first
configuration shown in Figure 5.1).
For the “ESR at each demand node” configuration, the pipe cost is minimum but
the ESR cost is maximum compared to any alternative configuration. In the case of a
single ESR, the ESR cost is minimum but the pipe cost is maximum. The cost optimum
ESR configuration therefore depends on the network topology and can lie anywhere at or
between these two extremes. For example in the sample network shown in Figure 5.1, the
capital cost is minimized if 3 ESRs are built.
In summary, the choice of ESR configuration, that is, the location, height and
capacity of the ESRs, and the set of demand nodes that each ESR serves, is a non-trivial
decision that has a direct impact on the capital cost optimization of piped water networks.
5.4 Model Details
Several variables are added to the model to implement ESR allocation. We briefly describe
the added variables and constraints below. Note that these variables and constraints are
in addition to those described in our previous model.
33
5.4.1 Variables
Continuous Variables:
tn : Height of ESR at node n
dn : Total demand served by ESR at node n
hn : Water head at node n
hli : Total headloss across link i
h0 ni : Effective head provided to link i by its starting node n
Binary Variables:
fi : 1 if flow in link i is primary, 0 if secondary
esni : 1 if source of water for link i is its immediate upstream node n, 0 otherwise
snm : 1 if ESR at node n is source for node m, 0 otherwise
enk : 1 if ESR at nth node is costed by the k th row of ESR cost table, 0 otherwise
Parameters:
N N : Number of nodes in the network
N E: Number of rows in the ESR cost table
Bk : Base cost of the k th row of the ESR cost table
U Nk : Unit cost of the k th row of the ESR cost table
U Pk : Upper limit capacity for the k th row of the ESR cost table
LOk : Lower limit capacity for the k th row of the ESR cost table
DE: The total water demand of the network
Tmin : Minimum ESR height allowed
Tmax : Maximum ESR height allowed
An : Set of nodes that are ancestors of node n
Dn : Set of nodes that are descendants of node n
34
Cn : Set of child nodes of node n
Pn : Parent node of node n
In : Incoming link for node n
On : Set of outgoing links from node n
F Lpi : Flow in ith link if i is part of the primary network
F Lsi : Flow in ith link if i is part of the secondary network
P H: Number of hours of water supply in the primary network
SH: Number of hours of water supply in the secondary network
5.4.2 Objective Cost
The additional objective cost term is simply the ESR cost at each node.
NL X
X NP NL X
X NP NN X
X NE
O(.) = Cij (Dij )lij + Li Cij (Dij )pij + enk ∗(Bk +U Nk ∗(dn −LOk )) .
i∈S∼E j=1 i∈SE j=1 n=1 k=1
(29)
5.4.3 Constraints
• Note that the ESR cost term is non-linear since it contains a product of two variables
enk ∗ di . But this term is linearizable since enk is a binary variable. We introduce
znk to represent enk ∗ di and add the following constraints:
znk ≤ DE ∗ enk , n = 1, . . . , N N, k = 1, . . . , N E , (30)

znk ≤ dn , n = 1, . . . , N N, k = 1, . . . , N E , (31)
znk ≥ dn − DE ∗ (1 − enk ) , n = 1, . . . , N N, k = 1, . . . , N E . (32)
Note that this will be a common occurrence in the constraints to come i.e. the
decomposition of a product of a continuous and a binary variable into linear con-
straints. For the sake of clarity and brevity the non-linear constraints will be men-
tioned as is.
• The first ESR constraint is to ensure that every ESR height tn is between constants
Tmin and Tmax .
Tmin ≤ tn ≤ Tmax , n = 1, . . . , N N . (33)
35
• Next the head constraint at each node is modified to include the ESR height.
Pn ≤ hn − tn − En , n = 1, . . . , N N . (34)
• We then look at the constraints that deal with allocation of demand nodes to ESRs.If
a node n does not serve its own demand i.e. it is part of a secondary network, then
all its downstream nodes will also be part of a secondary network.
smm ≤ snn , n = 1, . . . , N N, m ∈ Dn . (35)
• If a node n does not serve its own demand, then it cannot serve the demand of its
downstream nodes.
snm ≤ snn , n = 1, . . . , N N, m ∈ Dn . (36)
• For every node n, only one upstream node m can serve its demand.
X
smn = 1, n = 1, . . . , N N . (37)
m∈An ∪{n}
• The total demand dn served by node n is the sum of the demands of the downstream
nodes that it serves i.e. all m such that snm = 1.
X
dn = snm ∗ DEm , n = 1, . . . , N N . (38)
m∈Dn ∪{n}
• For a node n, its incoming pipe i will have primary flow only if the node serves
itself.
fi = snn , n = 1, . . . , N N, i = In . (39)
• If a node n serves node m i.e. snm = 1, each node o in the path from n to m belongs
to a secondary network and therefore cannot serve itself.
snm ≤ 1 − soo , n = 1, . . . , N N, m ∈ Dn , o ∈ Dn ∩ Am . (40)
• Next, we have the constraints that relate the demand that a ESR serves to its cost
variables enk . Note that we require znk in our objective function to replace the non
linear term enk × dn :
znk = enk × dn , n = 1, . . . , N N, k = 1, . . . , N E . (41)
• Since every ESR can be costed using exactly one row of the table, the sum of enk
for a given n must be 1:
NE
X
enk = 1, n = 1, . . . , N N . (42)
k=1
36
• Next we have constraints that make sure that the ESR capacity dn lies between the
minimum and maximum capacity of the selected row of the cost table:
F or n = 1, . . . , N N, k = 1, . . . , N E :
LOk enk ≤ dn , (43)
DE ∗ enk + dn ≤ U Pk + DE . (44)
• Across every link i there is headloss hli . This headloss depends on the flow, length
and diameter of the pipe chosen. As before, we use the Hazen-Williams equation
[74] to calculate the headloss. The flow through the link depends on whether the
link is part of the primary or secondary network:
NP
X
hli = (HLpij fi + HLsij (1 − fi ))lij , i = 1, . . . , N L ,
j=1
(45)
p 1.852

F Li
10.68 ∗ Rj
HLpij = , i = 1, . . . , N L, j = 1, . . . , N P ,
Dj4.87
(46)
s 1.852

F Li
10.68 ∗ Rj
HLsij = , i = 1, . . . , N L, j = 1, . . . , N P ,
Dj4.87
(47)
PH
F Lsi = F Lpi ∗ , i = 1, . . . , N L .
SH
(48)
Before the introduction of ESRs, the source node provided head to the entire net-
work. Therefore the head at each node was computed as the head provided by the
source minus the sum of all headlosses along the path from the source to the node.
But now each ESR serves the role of the source to the secondary network it is re-
sponsible for. The impact of the introduction of ESR is illustrated in Figure 5.2.
The source remains responsible for the primary network. Therefore for each link i
with a start node n:
hn = h0mi − hli , n = 1, . . . , N N, m = Pn , i = In ,
(49)
h0mi = (tm + Em ) ∗ esmi + hm ∗ (1 − esmi ), m = 1, . . . , N N, i ∈ Om ,
(50)
esmi = smm ∗ (1 − fi ), m = 1, . . . , N N, i ∈ Om .
(51)
37
esmi here represents if the secondary source of pipe i is node m. It is 1 only if node
m serves itself and if the flow in pipe i is secondary. If esmi is 1 then the effective
head served by node m is the sum of its elevation and the esr height. Else it is
simply the head provided by the upstream source.
Figure 5.2: Change in downstream head due to introduction of ESR.
The new model was tested on the sample network shown in 5.1. Apart from the optimal
configuration we looked at the cost breakup of the two extreme configurations, namely a
single ESR and ESRs at each demand point.
Table 5.2: Cost breakup of alternative ESR configurations.

Number ESR Cost Piping Cost Total Cost
Configurations
of ESRs (1000 Rs) (1000 Rs) (1000 Rs)
Single ESR 1 3703 20214 23917

ESR at every
6 7644 14642 22286
demand node
Optimal 3 5694 16041 21735
The results shown in table 5.2 are in line with expectations. The single ESR
configuration has the minimum ESR cost and the ESR at every node configuration has
the minimum piping cost. The overall optimal configuration however has both ESR and
piping cost in the middle but an overall lower cost.
We have looked at the two primary contributors to capital cost in a network, pipes
and ESRs. We next look at pumps which not only contribute to the capital cost of the
scheme but also the operational cost. Additionally with the introduction of pumps and
valves, the designer gains the ability to increase/decrease the head in the network.
38
Chapter 6
Pumps/Valves Integration
So far we have only looked at networks that have solely relied on gravity for the trans-
mission of water. But in most real life scenarios it is often the case that part of the
distribution network is at a higher elevation than the source. It might be possible to
increase the source head by constructing the MBR at a height but then this might put
a heavy load on the capital cost of the scheme. To ensure the high elevation locations
receive the water, one might be forced to employ pipes of large diameters that are very
expensive.
On the flip side there might be networks where the source is at a very high elevation
and therefore there is excessive pressure in the entire network despite using the smallest
pipe diameters. The problem with excess pressure is that it might lead to bursting of
pipes and as such higher resilience pipes may need to be employed which again increases
the capital cost.
To address the problems of too less or too much head, network components like
pumps and valves can be employed. Pumps help provide additional head to the network.
Up to now we have only considered the capital cost of the scheme. But with pumps an
important component of its cost, if not the most, is its operational cost. The energy
required to run the pump is a continuous cost that the scheme must bear. So with the
introduction of pumps, we must now consider the operational cost in addition to the
capital cost of the scheme.
6.1 Model Extension to Include Pumps

To include pumps in our model, we consider a pump being allowed at each pipe in the
network (unless user specifically says otherwise). What remains to be determined is the
power of each pump and the head provided by the pump. If the pump power selected
is 0, it means that a pump is not selected for that pipe. Also the pumps are assumed
to be operational for the entire duration of the supply. Therefore a pump in the pri-
39
mary/secondary network will run for the primary/secondary supply hours respectively.
As before the following objective cost terms, constraints and variables are in addition to
the ones already mentioned earlier.
6.1.1 Variables
pi : Power of pump installed at link i
ppi : Power of pump installed at link i, if link i is part of primary network
psi : Power of pump installed at link i, if link i is part of secondary network
phi : Head provided by pump at link i
Binary Variables:
pei : 1 if a pump is installed at link i, 0 otherwise
Parameters:
ρ: Density of water
g: Acceleration due to gravity
η: Efficiency of pump
P Pmin : Minimum pump power allowed
P Pmax : Maximum pump power allowed
IN F R: Inflation rate
IN T R: Interest rate
CP : Capital cost of pumps per unit kW
EP : Energy cost of pumps per unit kWh
DF : Discount factor for the energy cost over the entire scheme lifetime
40
6.1.2 Objective Function
Now that operational cost is also being considered, there are several ways to incorporate
it along with the capital cost. One possibility is optimizing for the operational cost
while considering capital cost as a constraint. This would be in line with schemes having
a fixed upper limit on their budget depending on the size of the population that they
serve. Another possibility is to consider both capital cost and operational cost in the
objective function. Here since the operational cost is borne across several years, the
effective operational cost used is after considering both the interest rate and the inflation
rate.
NL X
X NP NL X
X NP
O(.) = Cij (Dij )lij + Li Cij (Dij )pij
NN X
X NE
+ enk ∗ (Bk + U Nk ∗ (dn − LOk )) (52)
n=1 k=1
NL NL NL
!
X X X
+ CP ∗ pi + EP ∗ DF ∗ P H ∗ ppi + SH ∗ psi ,
i=1 i=1 i=1
Y n−1
X 1 + IN F R
where DF = .
n=1
1 + IN T R
6.1.3 Constraints
• The original headloss constraint is modified to include the artificial head provided
by the pump:
NP
X
hli = (HLpij fi + HLsij (1 − fi ))lij − pi , i = 1, . . . , N L . (53)
j=1
• Next we have to relate the head provided by the pump to its power. Head phi
provided by the pump is a continuous variable and the flow can take on two values
depending on whether the pipe is in the primary network or the secondary net-
work. Therefore we compute power as the sum of primary and secondary power
and compute each component separately.
pi = ppi + psi , i = 1, . . . , N L, (54)

(ρ ∗ g ∗ F Lpi ∗ phi )
ppi = ∗ fi , i = 1, . . . , N L, (55)
η
(ρ ∗ g ∗ F Lsi ∗ phi )
psi = ∗ (1 − fi ), i = 1, . . . , N L . (56)
η
41
• Finally, the pump power for each pump must lie between minimum and maximum
allowed pump power. This is implemented using the binary variable pei .
P Pmin ∗ pei ≤ pi ≤ P Pmax ∗ pei , i = 1, . . . , N L . (57)
Table 6.1: Cost breakup of alternative ESR configurations with pumps.

Number ESR Cost Piping Cost Pump Cost Total Cost
Configurations
of ESRs (1000 Rs) (1000 Rs) (1000 Rs) (1000 Rs)
Single ESR 1 3703 20214 0 23917

ESR at every
6 7644 14642 0 22286
demand node
Optimal 3 5694 16041 0 21735

Optimal with
2 4856 13628 2132 20615
Pumps
As in section 5.4.4, the model including pumps was tested on the sample network shown
in figure 5.1. Along with the different ESR configurations, we now compare the cost once
pumps are allowed as well. As can be seen in table 6.1, the inclusion of pumps has resulted
in a further decrease in overall cost. This is due to a significant decrease in piping cost
since pipes of lesser diameters could be utilized.
6.2 Model Extension to Include Valves

The introduction of pressure reducing valves reduces the downstream head along the pipe
they are installed, hence reducing excess pressure in the network. But from the optimiza-
tion perspective if no penalties or constraints are included to “punish” excess pressure, the
valves will never be chosen by the model. Currently the notion of excess pressure being a
negative is purely an external to the model notion. Based on discussions with government
engineers, we have decided to not strictly enforce any maximum pressure constraints since
in some cases (like hilly areas) it might be unavoidable. Thus, to incorporate pressure re-
ducing valves we have included a manual option where the user can introduce for any link
i a valve with pressure reducing setting V Hi . The headloss equation therefore becomes:
NP
X
hli = (HLpij fi + HLsij (1 − fi ))lij − pi + V Hi , i = 1, . . . , N L . (58)
j=1
With the inclusion of ESRs, pumps and valves the complexity of the model increased
significantly leading to poor performance on larger networks. In order to address this, the
a series of improvements to the model were made which are described in the next chapter.
42
Chapter 7
Model Improvements
The first version of the model included just the pipe diameter optimization for branched
networks (typical in the case of rural areas). It was a LP model and thus solved the
problem quickly and optimally. This allowed even networks of a thousand nodes to be
solved in a couple of seconds. We extended the model to include ESRs. The added
complexity of considering both primary and secondary networks simultaneously, required
an ILP model. Although still optimal in terms of cost, the time taken was significantly
worse. In this chapter we describe three significant improvements that were made to the
model. These improvements reduced the time taken to optimize the larger networks by
orders of magnitude. The time taken to optimize a 150 node network has gone from over
40 minutes to 5 seconds, and a 200 node network which could not be solved within 24
hours now takes just 70 seconds.
b e
a
S
S2
d
c
Figure 7.1: Tightening linear relaxation by introducing constraint.
The improvements consist of tightening the set of constraints used to describe the
ILP model. Consider the example shown in figure 7.1. The points represent the integer
points over which we are trying to optimize. The lines a, b, c, d and e represent the
constraints that encompass those integer points. When solving the linear point (LP)
relaxation, the entire set S is considered. By introducing the constraint e, we can still
capture the same integer points while cutting off a part (S2 ) of the linear relaxation. Since
a smaller solution space is now considered while solving the LP relaxation, this speeds up
43
the optimization. For each of the three improvements presented, we prove that the newer
set of constraints have a linear relaxation that is a strict subset of the linear relaxation
of the older set, while maintaining the same set of integer points. In particular, for the
ESR configuration improvement we show that the newer subset of constraints is as tight
as possible, i.e. the linear relaxation has no fractional points. Since the overall model is
complex, while discussing each improvement, we only consider a small subset of relevant
constraints at a time.
7.1 Pipe Headloss Improvement
7.1.1 Initial Model
We first focus on a part of the model whose purpose is to determine the pipe diameters
chosen for each link in the network. Each link can consist of multiple pipe diameters. Also,
each link can be part of the primary network or the secondary network. The headloss
across the link depends on these choice of pipe diameters and whether it belongs to the
primary or secondary network. The set of variables and parameters used for this purpose
are defined as follows. Consider a network of N L links. Let N P be the number of pipe
diameters available.
Variables:
lij = length of the j th pipe diameter component of link i, i = 1, . . . , N L, j=

1, . . . , N P ,
p
lij = length of the j th pipe diameter component of link i, if link i is part of the
primary network, i = 1, . . . , N L, j = 1, . . . , N P ,
hli = headloss across link i, i = 1, . . . , N L,
fi = 1 of link i is part of the primary network, 0 if it is part of the secondary

network, i = 1, . . . , N L.
Parameters:
Li = Length of link i, i = 1, . . . , N L,
HLpij = Unit headloss for the j th pipe diameter component of link i, if i is part of
primary network, i = 1, . . . , N L, j = 1, . . . , N P ,
HLsij = Unit headloss for the j th pipe diameter component of link i, if i is part of
secondary network, i = 1, . . . , N L, j = 1, . . . , N P .
44
Constraints:
p
The first constraint captures lij as a product of lij and fi :
p
lij = lij × fi , i = 1, . . . , N L, j = 1, . . . , N P. (59)
Equation (59) consists of a product of two variables, and is therefore a non linear
equation. Fortunately since fi is a binary variable, we can linearize the equation using
the following inequalities:
p
0 ≤ lij , i = 1, . . . , N L, j = 1, . . . , N P, (60)
p
lij ≤ Li fi , i = 1, . . . , N L, j = 1, . . . , N P, (61)
p
lij − Li (1 − fi ) ≤ lij , i = 1, . . . , N L, j = 1, . . . , N P, (62)
p
lij ≤ lij , i = 1, . . . , N L, j = 1, . . . , N P. (63)
The sum of all pipe diameter components must equal the link length:
NP
X
lij = Li , i = 1, . . . , N L. (64)
j=1
Next we have the equation for hli , which is the sum all headloss components con-
tributed by the different pipe diameter components of link i :
NP
X NP
X
p p
hli = Pij lij + Sij (lij − lij ), i = 1, . . . , N L. (65)
j=1 j=1
Finally we have constraints that relate to the bounds for the variables:
lij ≥ 0, i = 1, . . . , N L, j = 1, . . . , N P, (66)

fi ∈ 0, 1 , i = 1, . . . , N L. (67)
p
Since there exists a lij for each link and pipe diameter combination in the network,
a large number of linear decompositions of equation (59) need to be done. In the next
section we show an improved model that has the same feasible 0-1 set of values but with
a tighter LP relaxation, resulting in better performance.
7.1.2 Improved Model (Model-2)
In order to decompose the product of variables in (59), a large number of constraints need
p
to be added. This is avoided in the new model by not explicitly defining lij . Instead its
relation to lij and fi is implicit. In the next section we show that new model is better.
45
Variables:
p
We introduce one new variable, which is similar to lij but for the secondary network:
s
lij = length of the j th pipe diameter component of link i, if link i is part of the secondary
network, and 0 if link i is part of the primary network i = 1, . . . , N L, j = 1, . . . , N P .
Constraints:
The first constraint simply states that lij is the sum of the primary and secondary
p s
components, i.e. lij and lij respectively:
p s
lij = lij + lij , i = 1, . . . , N L, j = 1, . . . , N P. (68)
p s
For a given link i, either all lij are 0 or all lij are 0, depending on the value of fi .
And the sum of the non-zero components must equal the length of the link Li . The first
two inequalities of the new model capture this:
NP
X p
lij = Li fi , i = 1, . . . , N L, (69)
j=1
NP
X
s
lij = Li (1 − fi ), i = 1, . . . , N L. (70)
j=1
Next we have the equation for hli , which is the sum all headloss components con-
tributed by the different pipe diameter components of link i. For the new model we
s p
equivalently use lij instead of lij − lij due to equation (68):
NP
X NP
X
p s
hli = Pij lij + Sij lij , i = 1, . . . , N L. (71)
j=1 j=1
Finally as before we have the bounds for the variables:
lij ≥ 0, i = 1, . . . , N L, j = 1, . . . , N P, (66)
p
lij ≥ 0, i = 1, . . . , N L, j = 1, . . . , N P, (60)
s
lij ≥ 0, i = 1, . . . , N L, j = 1, . . . , N P, (72)

fi ∈ 0, 1 , i = 1, . . . , N L. (67)
We now prove that the improved model is tighter than the initial model, that is the
linear relaxation of the improved model is a strict subset of the linear relaxation of the
initial model. Let S1 be the set of points belonging to the initial model and S2 be the set of
points belonging to the improved model. Let R1 and R2 be the set of points corresponding
to the LP relaxations of S1 and S2 respectively. Both R1 and R2 are defined by the same
set of constraints that describe the initial sets S1 and S2 , except for the constraint (67)
46
which refers to the binary nature of fi . Instead, the continuous bounds for fi is defined
as follows:
0 ≤ fi ≤ 1, i = 1, . . . , N L. (73)
Proposition 1. R2 is a strict subset of R1 i.e. R2 ⊂ R1 .
We prove R2 is a strict subset of R1 in two steps. First we show that R2 is a subset

of R1 and then we find a point in R1 that is not in R2 .
Consider a point P ∈ R2 . It satisfies the constraints (60), (66) and (68) - (73). We
prove that it also lies in R1 by showing that it satisfies the constraints (60)-(66) and (73).
Constraints (60), (66) and (73) are trivially satisfied since they are common for both sets.
F or i = 1, . . . , N L, j = 1, . . . , N P
p
Proving (61) : lij ≤ Li fi
NP
X p
lij = Li fi (69)
j=1
p
≡ {using lij ≥ 0 (60)}
p
lij ≤ Li fi
Hence satisfied.
p
Proving (62) : lij − Li (1 − fi ) ≤ lij
NP
X
s
lij = Li (1 − fi ) (70)
j=1
s
⇒ {using lij ≥ 0 (72)}
s
lij ≤ Li (1 − fi )
p s
≡ {using lij = lij + lij (68)}
p
lij − lij ≤ Li (1 − fi )
≡ {rearranging}
p
lij − Li (1 − fi ) ≤ lij
Hence satisfied.
p
Proving (63) : lij ≤ lij
s
0 ≤ lij (72)
p s
47
p
0 ≤ lij − lij
≡ {rearranging}
p
lij ≤ lij
Hence satisfied.
NP
X
Proving (64) : lij = Li
j=1
NP
X p
lij = Li fi (69)
j=1
NP
X
s
lij = Li (1 − fi ) (70)
j=1
≡ {adding equations}
NP
X p s
(lij + lij ) = Li fi + Li (1 − fi )
j=1
p s
≡ {using lij = lij + lij (68) and simplifying}
NP
X
lij = Li
j=1
Hence satisfied.
NP
X NE
X
p s
Proving (65) : hli = Pij lij + Sij (lij − lij )
j=1 j=1
NP
X NP
X
p s
hli = Pij lij + Sij lij (71)
j=1 j=1
p s
NP
X NE
X
p s
hli = Pij lij + Sij (lij − lij )
j=1 j=1
Hence satisfied.
Therefore point P ∈ R1 , since it satisfies the constraints (60)-(66) and (73). There-
fore R2 ⊆ R1 .
/ R2 . Take point Q(l, lp , ls , hl, f ) =

Next we find a point Q such that Q ∈ R1 and Q ∈
([L/2, L/2], [L/2, L/2], [0, 0], L, 1/2). Here (n, m) = (1, 2) and (L, P, S) = (L, [1, 1], [1, 1])
48
where L ≥ 0. We show Q ∈ R1 since it satisfies all the constraints.
60 :
p
0 ≤ l11 , replacing values we get 0 ≤ L/2
p
0 ≤ l12 , replacing values we get 0 ≤ L/2
61 :
p
l11 ≤ L1 f1 , replacing values we get L/2 ≤ L/2
p
l12 ≤ L1 f1 , replacing values we get L/2 ≤ L/2
62 :
p
l11 − L1 (1 − f1 ) ≤ l11 , replacing values we get
L/2 − L(1 − 1/2) ≤ L/2
p
l12 − L1 (1 − f1 ) ≤ l12 , replacing values we get
L/2 − L(1 − 1/2) ≤ L/2
63 :
p
l11 ≤ l11 , replacing values we get L/2 ≤ L/2
p
l12 ≤ l12 , replacing values we get L/2 ≤ L/2
64 :
l11 + l12 = L1 , replacing values we get L/2 + L/2 = L
65 :
p p p p
hl1 = P11 l11 + P12 l12 + S11 (l11 − l11 ) + S12 (l12 − l12 ),
replacing values we get L = L/2 + L/2 + 0 + 0
66 :
l11 ≥ 0, replacing values we get L/2 ≥ 0
l12 ≥ 0, replacing values we get L/2 ≥ 0
73 :
0 ≤ f1 ≤ 1, replacing values we get 0 ≤ 1/2 ≤ 1/2
49
Therefore point Q ∈ R1 . To show that Q ∈
/ R2 consider equation 70:
s s
l11 + l12 = L1 (1 − f1 ), replacing values we get 0 + 0 = L/2
Therefore Q ∈
/ R2 . We showed that R2 ⊆ R1 and that R2 6= R1 . These two
together imply R2 ⊂ R1 . Proposition 1 therefore shows that the LP relaxation of the new
model (R2 ) has a tighter bound than the LP relaxation of the old model (R1 ).
7.2 ESR Cost Improvement
7.2.1 Initial Model
We next focus on a part of the model whose purpose is to determine the capital cost of
each ESR in the network. The ESR cost is a piece-wise linear function. An example is
shown in figure 7.2 below. We need to determine which row in the ESR cost table the ESR
capacity falls in. Each row in the ESR cost table has minimum and maximum capacity
values. If the ESR capacity is within these values, then that row is used to compute the
ESR’s cost. In the example below if a ESR capacity of 5 litres is to be built, then the
first row of the cost table will be used, since its capacity range is 0-10. Binary variables
are used to capture for each ESR, the row in the cost table that is chosen to compute
the cost. The set of variables and parameters used for this purpose are defined as follows.
Consider a network of n locations. Let m be the number of linear components of the
piecewise linear cost of construction of a ESR.
200
Cost(Rs)
150
100
50
Capacity(litres)
5 10 15 20 25 30
Figure 7.2: Graph of the cost of a ESR vs its capacity.
50
Variables:
enk = 1 if the ESR at location n is costed using the k th row of the ESR cost table,
n = 1, . . . , N N, k = 1, . . . , N E,
znk = capacity of the ESR at location n if it is costed using the k th row of the ESR
cost table, 0 otherwise, n = 1, . . . , N N, k = 1, . . . , N E,
dn = capacity of ESR at location n, n = 1, . . . , N N .
Parameters:
LOk = minimum capacity that the k th row of the ESR cost table can satisfy, k=
1, . . . , N E,
U Pk = maximum capacity that the k th row of the ESR cost table can satisfy, k=
1, . . . , N E,
DE = value of the total water demand in the network, where DE ≥ U Pk , k =

1, . . . , N E.
Constraints:
The first constraint relates the ESR capacity corresponding to the k th row as a product
of the ESR capacity and the binary choice variable enk :
znk = enk × dn , n = 1, . . . , N N, k = 1, . . . , N E. (74)
Since equation (74) consists of a product of two variables, it is a non linear equation.
We linearize the equation using the following inequalities:
0 ≤ znk , n = 1, . . . , N N, k = 1, . . . , N E, (74.a)
znk ≤ DEenk , n = 1, . . . , N N, k = 1, . . . , N E, (74.b)
dn − DE(1 − enk ) ≤ znk , n = 1, . . . , N N, k = 1, . . . , N E, (74.c)
znk ≤ dn , n = 1, . . . , N N, k = 1, . . . , N E. (74.d)
Since every ESR can be costed using exactly one row, the sum of enk for a given n
must be 1:
NE
X
enk = 1, n = 1, . . . , N N. (75)
k=1
Next we have constraints that make sure that the ESR capacity dn lies between
the minimum and maximum capacity of the selected row of the cost table:
LOk enk ≤ dn , n = 1, . . . , N N, k = 1, . . . , N E, (76)
51
DEenk + dn ≤ U Pn + DE, n = 1, . . . , N N, k = 1, . . . , N E. (77)
Finally we have constraints that relate to the bounds for the variables:
DE ≥ dn , n = 1, . . . , N N, (78)
dn ≥ 0, n = 1, . . . , N N, (79)

enk ∈ 0, 1 , n = 1, . . . , N N, k = 1, . . . , N E. (80)
Since there exists a znk for each ESR and row of cost table combination, a large
number of linear decompositions of equation (74) need to be done. This results in poor
performance of the model. In the next section we show an improved model that has the
same feasible 0-1 set of values but with a tighter LP bound resulting in better performance.
As discussed in the previous section, the main issue with the old model was equation
(74), where zn k is expressed as a product of two variables. In order to decompose the
variables, a large number of constraints needed to be added. This is avoided in the new
model by not explicitly defining znk . Instead its relation to enk and dn is implicit. In the
next section we first show that new model is better in that it has a tighter LP bound
than the old model and then we go on to show that the LP for the new model has tight
solutions.
The variables remain same for the new model. The first two inequalities of the
model provide the bounds for znk in terms of enk and the minimum (LOk ) and maximum
(U Pk ) capacities for each row of the cost table:
LOk enk ≤ znk , n = 1, . . . , N N, k = 1, . . . , N E, (81)

znk ≤ U Pk enk , n = 1, . . . , N N, k = 1, . . . , N E. (82)
The next equation for the model remains unchanged, it represents the fact that
each row of the cost table is chosen exactly once for each ESR:
NE
X
enk = 1, n = 1, . . . , N N. (75)
k=1
Next, we have a similar equation but this time related to the variable znk . The
sum of all znk values for a given ESR must equal dn :
NE
X
znk = dn , n = 1, . . . , N N. (83)
k=1
In fact along with the previous three equations of the model, one can imply that
exactly one of the znk values will be non zero for a specific ESR and therefore will be
52
equal to dn . This therefore captures the non-linear constraint that equation (74) of the
old model captured. The remaining constraints relate to the bounds for the variables:
DE ≥ dn , n = 1, . . . , N N, (78)

enk ∈ 0, 1 , n = 1, . . . , N N, k = 1, . . . , N E, (80)
dn ≥ 0, n = 1, . . . , N N, (79)
znk ≥ 0, n = 1, . . . , N N, k = 1, . . . , N E. (74.a)
Let S1 be the set of points belonging to the old model and S2 be the set of points
belonging to the new model. Let R1 and R2 be the set of points corresponding to the LP
relaxations of S1 and S2 respectively.The continuous bounds for enk is defined as follows:
0 ≤ enk ≤ 1, n = 1, . . . , N N, k = 1, . . . , N E. (84)
As in Section 7.1, we prove that the LP relaxation of the new model is tighter than
the LP relaxation of the old model. We next show that R2 has no fractional corner points
and thus cannot be tightened further.
Proposition 2. R2 is a strict subset of R1 i.e. R2 ⊂ R1
As in Proposition 1, we prove R2 is a strict subset of R1 in two steps. First we

show that R2 is a subset of R1 and then we show that R2 is not equal to R1 .
Consider a point P ∈ R2 . It satisfies the constraints (74.a), (75) and (78)-(84).
We prove that it also lies in R1 by showing that it satisfies the constraints (74.a)-(79)
and (84). Constraints (74.a), (75), (78)-(79) and (84) are trivially satisfied since they are
common for both sets.
F or n = 1, . . . , N N, k = 1, . . . , N E
Proving (74.b) : znk ≤ DEenk

znk ≤ U Pk enk (82)
⇒ {using DE ≥ U Pk (definition)}
znk ≤ DEenk
Hence satisfied.
Proving (74.c) : dn − DE(1 − enk ) ≤ znk

NE
X
znk0 = dn (83)
k0 =1
53
≡ {splitting sum}
NE
X
znk + znk0 = dn
k0 =1,k0 6=k
≡ {rearranging}
NE
X
znk0 = dn − znk (85)
k0 =1,k0 6=k
NE
X
enk0 = 1, (75)
k0 =1
≡ {splitting sum}
NE
X
enk + enk0 = 1
k0 =1,k0 6=k
≡ {rearranging}
NE
X
enk0 = 1 − enk , (86)
k0 =1,k0 6=k
znk ≤ DEenk (74.b)

⇒ {sum over k 0 }
NE
X NE
X
znk0 ≤ DE enk0
k0 =1,k0 6=k k0 =1,k0 6=k
≡ {using (85), (86)}

dn − znk ≤ DE(1 − enk )
≡ {rearranging}
dn − DE(1 − enk ) ≤ znk
Hence satisfied.
Proving (74.d) : znk ≤ dn

NE
X
znk = dn , (83)
k=1
⇒ {using 0 ≤ znk (74.a)}

znk ≤ dn
Hence satisfied.
54
Proving (76) : LOk enk ≤ dn
LOk enk ≤ znk (81)
⇒ {using znk ≤ dn (74.d)}
LOk enk ≤ dn
Hence satisfied.
Proving (77) : dn + DEenk ≤ U Pk + DE

dn − DE(1 − enk ) ≤ znk (74.c)
⇒ {using znk ≤ U Pk enk (82)}
dn − DE + DEenk ≤ U Pk enk
⇒ {using 0 ≤ enk ≤ 1 (84)}
dn − DE + DEenk ≤ U Pk
≡ {rearranging}
dn + DEenk ≤ U Pk + DE
Hence satisfied.
Therefore point P ∈ R1 and R2 ⊆ R1 .

Next we find a point Q such that Q ∈ R1 and Q ∈
/ R2 . Take a point Q(z, e, d) =
([d, d], [1/2, 1/2], d). Here (n, m) = (1, 2), (LOk , U Pk , DE) = ([0, d], [d, 2d], 2d) where
d ≥ 0. We show Q ∈ R1 since it satisfies the constraints (74.a)-(79) and (84).
74.a :
0 ≤ z11 , replacing values we get 0 ≤ d
0 ≤ z12 , replacing values we get 0 ≤ d
74.b :
z11 ≤ DEe11 , replacing values we get d ≤ 2d/2
z12 ≤ DEe12 , replacing values we get d ≤ 2d/2
74.c :
d1 − DE(1 − e11 ) ≤ z11 , replacing values we get
d − 2d(1 − 1/2) ≤ d
55
d1 − DE(1 − e12 ) ≤ z12 , replacing values we get
d − 2d(1 − 1/2) ≤ d
74.d :
z11 ≤ d1 , replacing values we get d ≤ d
z12 ≤ d1 , replacing values we get d ≤ d
75 :
e11 + e12 = 1, replacing values we get 1/2 + 1/2 = 1
76 :
LO1 e11 ≤ d1 , replacing values we get 0 × 1/2 ≤ d
LO2 e12 ≤ d1 , replacing values we get d × 1/2 ≤ d
77 :
DEe11 + d1 ≤ U P1 + DE, replacing values we get
2d × 1/2 + d ≤ d + 2d
DEe12 + d1 ≤ U P2 + DE, replacing values we get
2d × 1/2 + d ≤ 2d + 2d
78 :
DE ≥ d1 , replacing values we get 2d ≥ d
84 :
0 ≤ e11 ≤ 1, replacing values we get 0 ≤ 1/2 ≤ 1
0 ≤ e12 ≤ 1, replacing values we get 0 ≤ 1/2 ≤ 1
Therefore point Q ∈ R1 . To show that Q ∈

/ R2 consider equation 83:
z11 + z12 = d, replacing values we get d + d = 2d
Therefore Q ∈
/ R2 and R2 ⊂ R1 . Proposition 2 therefore shows that the LP
relaxation of the new model (R2 ) has a tighter bound than the LP relaxation of the old
model (R1 ).
56
We next show that in fact R2 has the tightest relaxation possible by showing that
a point with fraction value for enk will never be a corner point.
Proposition 3. If point P ∈ R2 has a fractional value for enk , P cannot be a corner

point of R2 .
Proof. Consider a point P (z, e, d) ∈ R2 with at least one fractional value for enk i.e.
0 < en0 k0 < 1 for some n0 , k 0 . Let en0 k0 = t. Construct another point P1 that has the same
components of P for n 6= n0 . For n = n0 take (z, e, d) as follows:
F or k = 1, . . . , N E
zn0 k0 = 0
znP0 k
zn0 k = , f or k 6= k 0
1−t
en0 k0 = 0
ePn0 k
en0 k = , f or k 6= k 0
1−t
dP0 − znP0 k0
dk0 = n
1−t
Here znP0 k0 , ePn0 k0 , dPn0 are the corresponding values of point P . We show that P1 ∈ R2
since it satisfies all the constraints:
81 :
LOk0 en0 k0 ≤ zn0 k0
≡ LOk0 × 0 ≤ 0 (definition)
LOk en0 k ≤ zn0 k , k 6= k 0

ePn0 k z P0
≡ LOk ≤ nk , k 6= k 0 (definition)
1−t 1−t
≡ LOk ePn0 k ≤ znP0 k , k 6= k 0 (0 < t < 1)
Satisfied since P ∈ R2 .
82 :
zn0 k0 ≤ U Pk0 en0 k0
≡ 0 ≤ U Pk 0 × 0 (definition)
57
zn0 k ≤ U Pk en0 k , k 6= k 0
znP0 k eP0
≡ ≤ U Pk n k , k 6= k 0 (definition)
1−t 1−t
≡ znP0 k ≤ U Pk ePn0 k , k 6= k 0 (0 < t < 1)
Satisfied since P ∈ R2 .
75 :
NE
X
en0 k
k=1
NE
X
=0+ en0 k (splitting sum)
k=1,k6=k0
NE
X ePn0 k
= (definition)
k=1,k6=k0
1−t
NE
1 − ePn0 k0 X
= ( ePn0 k = 1)
1−t k=1
1−t
= (definition)
1−t
=1 (0 < t < 1)
83 :
NE
X
zn0 k
k=1
NE
X
=0+ zn0 k (splitting sum)
k=1,k6=k0
NE
X znP0 k
= (definition)
k=1,k6=k0
1−t
NE
dPn0 − ePn0 k0 X
= ( znP0 k = dPn0 )
1−t k=1
= dn0 (definition)
84 :
NE
X
ePn0 k = 1 (P ∈ R2 )
k=1
58
NE
X
≡ ePn0 k0 + ePn0 k = 1 (splitting sum)
k=1,k6=k0
NE
X
≡ t+ ePn0 k = 1 (definition)
k=1,k6=k0
NE
X
≡ ePn0 k = 1 − t (rearranging)
k=1,k6=k0
≡ 0 ≤ ePn0 k ≤ 1 − t, k 6= k 0 (ePn0 k ≥ 0)
ePn0 k
≡0≤ ≤ 1, k 6= k 0 (1 − t > 0)
1−t
≡ 0 ≤ en0 k ≤ 1, k 6= k 0 (definition)
79 :
NE
X
znP0 k = dPn0 (P ∈ R2 )
k=1
NE
X
≡ znP0 k0 + znP0 k = dPn0 (splitting sum)
k=1,k6=k0
NE
X
≡ znP0 k = dPn0 − znP0 k0 (rearranging)
k=1,k6=k0
≡ dPn0 − znP0 k0 ≥ 0 (znP0 k ≥ 0)

dPn0 − znP0 k0
≡ ≥0 (1 − t > 0)
1−t
≡ dn0 ≥ 0 (definition)
74.a :
znP0 k ≥ 0, k 6= k 0 (P ∈ R2 )
znP0 k
≡ ≥ 0, k 6= k 0 (1 − t > 0)
1−t
≡ zn0 k ≥ 0, k 6= k 0 (definition)
Therefore P1 ∈ R2 .
Similar to P1 construct point P2 having the same components as P for n 6= n0 . For
n = n0 take (z, e, d) as follows:
F or k = 1, . . . , N E
59
znP0 k0
zn0 k0 =
t
zn0 k = 0 f or k 6= k 0
en0 k0 = 1
en0 k = 0 f or k 6= k 0
znP0 k0
dn0 =
t
As before znP0 k0 , ePn0 k0 , dPn0 are the corresponding values of point P . We show that
P2 ∈ R2 since it satisfies all the constraints:
81 :
LOk0 ePn0 k0 ≤ znP0 k0 (P ∈ R2 )
≡ LOk0 × t ≤ znP0 k0 (definition)
znP0 k0
≡ LOk0 ≤ (0 < t)
t
≡ LOk0 ≤ zn0 k0 (definition)
≡ LOk0 × 1 ≤ zn0 k0
≡ LOk0 en0 k0 ≤ zn0 k0 (definition)
LOk en0 k ≤ zn0 k , k 6= k 0

≡ LOk × 0 ≤ 0, k 6= k 0 (def inition)
82 :
znP0 k0 ≤ U Pk0 ePn0 k0 (P ∈ R2 )
≡ znP0 k0 ≤ U Pk0 × t (definition)
znP0 k0
≡ ≤ U Pk 0 (0 < t)
t
≡ zn0 k0 ≤ U Pk0 × 1 (definition)
≡ zn0 k0 ≤ U Pk0 en0 k0 (definition)
zn0 k ≤ U Pk en0 k , k 6= k 0
≡ 0 ≤ U Pk × 0, k 6= k 0 (definition)
75 :
60
NE
X
en0 k
k=1
NE
X
= en0 k0 + en0 k (splitting sum)
k=1,k6=k0
=1+0 (definition)
83 :
NE
X
zn0 k
k=1
NE
X
= zn0 k0 + zn0 k (splitting sum)
k=1,k6=k0
znP0 k0
= +0 (definition)
t
= dn0 (definition)
84 :
en0 k0 = 1 (definition)
en0 k = 0, k 6= k 0 (definition)
79 :
znP0 k0 ≥ 0 (P ∈ R2 )
znP0 k0
≡ ≥0 (0 < t)
t
≡ dn0 ≥ 0 (definition)
74.a :
znP0 k0 ≥ 0 (P ∈ R2 )
znP0 k0
≡ ≥0 (0 < t)
t
≡ zn0 k0 ≥ 0 (definition)
zn0 k ≥ 0, k 6= k 0
≡ 0 ≥ 0, k 6= k 0 (definition)
61
Therefore P2 ∈ R2 .
znP0 k eP0 d0P − znP0 k0

P1 = (( , 0), ( n k , 0), i )
1−t 1−t 1−t
z P0 0 z P0 0
P2 = ((0, n k ), (0, 1), n k )
t t
⇒ P1 (1 − t) + P2 t = ((zn0 k , zn0 k0 ), (en0 k , t), d0P
P P P
i )
=P
Since P can be represented as a linear combination of two other points belonging

to R2 , P cannot be a corner point of R2 . This implies that LP relaxation (R2 ) of the
new model will provide only integer solutions. Therefore, the new model has a tight
relaxation.
7.3 ESR Configuration Improvement

For a given network of nodes and links, one aspect of the problem is to determine the
location of ESRs and the set of downstream nodes that are to be served by each ESR.
We need a set of constraints to model a valid network configuration. In the following
section we repeat the set of constraints that model such a network as laid out earlier. We
then show that the model is not tight, i.e. its linear relaxation is not guaranteed to have
integral corner points. In Section 7.3.2 we then describe an improved model and prove its
tightness.
7.3.1 Initial Model
Consider a tree network of n nodes.
Parameters:
An = Set of ancestor nodes of node n, n = 1, . . . , N N .
Dn = Set of descendant nodes of node n, n = 1, . . . , N N .
Cn = Set of child nodes of node n, n = 1, . . . , N N .
Pn = Parent node of node n, n = 1, . . . , N N .
Variables:
snm = 1 if ESR at nth node serves the demand of mth node, n = 1, . . . , NN,
m ∈ Dn ∪ {n}.
62
Constraints:
We can use the following set of constraints to describe the set of valid network config-
urations as described earlier:
smm ≤ snn , n = 1, . . . , N N, m ∈ Dn , (87)

snm ≤ snn , n = 1, . . . , N N, m ∈ Dn , (88)
X
smn = 1, n = 1, . . . , N N, m ∈ An ∪ {n}, (89)
m
snm ≤ 1 − soo , n = 1, . . . , N N, m ∈ Dn , o ∈ Dn ∪ Am , (90)

snm ∈ 0, 1 , n = 1, . . . , N N, m ∈ Dn ∪ {n}. (91)
Proposition 4. The linear relaxation of S is not tight.
Proof. Let the linear relaxation of set S be R. Instead of constraint (91) we will have the
following constraint:
0 ≤ snm ≤ 1, n = 1, . . . , N N, m ∈ Dn ∪ {n}. (92)
Consider a small network of 3 nodes with node 1 as root and node 2 child of node
1, and node 3 child of node 2. For a point to belong to R, the following constraints must
be met:
s22 ≤ s11 , (87.a)

s33 ≤ s11 , (87.b)
s33 ≤ s22 , (87.c)
s12 ≤ s11 , (88.a)
s13 ≤ s11 , (88.b)
s23 ≤ s22 , (88.c)
s11 = 1, (89.a)
s12 + s22 = 1, (89.b)
s13 + s23 + s33 = 1, (89.c)
s13 ≤ 1 − s22 , (90.a)
0 ≤ s11 , s12 , s13 , s22 , s23 , s33 ≤ 1. (92)
Since s11 = 1, we replace its value in the constraints and replace repeating constraints to
get the following set:
s33 ≤ s22 , (87.c)

s23 ≤ s22 , (88.c)
63
s11 = 1, (89.a)
s12 + s22 = 1, (89.b)
s13 + s23 + s33 = 1, (89.c)
s13 ≤ 1 − s22 , (90.a)
0 ≤ s12 , s13 , s22 , s23 , s33 ≤ 1. (92)
Consider a point P defined as:

P {s11 , s12 , s13 , s22 , s23 , s33 } = {1, 21 , 0, 12 , 21 , 12 }. Since it satisfies all the constraints, P ∈ R.
We now show that P cannot be described as a linear combination of two distinct points
that belong to R.
Consider two points Q1 , Q2 ∈ R such that:
P = tQ1 + (1 − t)Q2 , 0<t<1
sQ 1 Q2
11 = s11 = 1 {89.a}
sP13 = 0 {definition}
⇒sQ 1 Q2
13 = s13 = 0 {92.c} (93)
s33 + s23 ≤ 2s22 {adding 87.c and 88.c}

⇒1 − sQ Q1
13 ≤ 2s22
1
{89.c}
1
⇒ ≤ sQ 22
1
{93}
2
1
⇒ ≤ sQ 22
2
{Similarly}
2
1 1
⇒sQ 1 Q2
22 = s22 = {sP22 = } (94)
2 2
s12 + s22 = 1 {89.b}

1
⇒sQ 1 Q2
12 = s12 = {94}
2
s33 ≤ s22 {87.c}

1
⇒sQ
33 ≤
1
{94}
2
s23 ≤ s22 {88.c}
1
⇒sQ
23 ≤
1
{94}
2
64
1
⇒sQ 1 Q1
23 = s33 = {89.c}
2
1
⇒sQ 2 Q2
23 = s33 = {Similarly}
2
Therefore P = Q1 = Q2 . Since P cannot be expressed as a linear combination of two
distinct points, P is a corner point of R. And since P contains non-integral values for
snm , relaxation R is not tight.
A new model is proposed which although maintains the same structure as the initial
model, it does so using tighter constraints. The primary insight about the structure is
expressed in the second constraint mentioned below. A node i serves its child j if and
only if it serves all the nodes downstream of j. Consider set S2 defined by the following
set of constraints:
X
smn = 1, n = 1, . . . , N N, m ∈ An ∪ {n}, (89)
m
snm = snk , n = 1, . . . , N N, m ∈ Cn , k ∈ Dm , (95)

snm ∈ 0, 1 , n = 1, . . . , N N, m ∈ Dn ∪ {n}. (91)
Proposition 5. The linear relaxation of S2 is tight.
Proof. Let the linear relaxation of set S2 be R2 . Instead of constraint (91) we will have
the following constraint:
0 ≤ snm ≤ 1, n = 1, . . . , N N, m ∈ Dn ∪ {n}. (96)
We will show that R2 is tight by showing any point P, with a non-integer component
can be expressed as a linear combination of two distinct points from R2 .
Consider a point P ∈ R2 with 0 < sn0 n0 = t < 1 for some n0 . Let n0 be the first such node
in the path from root.
Claim 5.1. snn = 1, n ∈ An0
Proof. snn cannot be fractional since n0 is the first such node from root by definition.
Assume snn = 0 for some n ∈ An0 .
Let Enn0 = (Dn ∪ {n}) ∩ (A0n ∪ {n0 }).
snn = 0
X
≡ {using smn = 1 (89)}
m
65
X
smn = 1 m ∈ An
m
X
smn0 = 1 m ∈ A0n ∪ {n0 }
m
≡ {splitting sum}
X X
smn0 + skn0 = 1 m ∈ An , k ∈ Enn0
m k
≡ {using snm = snk (95)}

X X
smn + skn0 = 1 m ∈ An , k ∈ Enn0
m k
X
≡ {using smn = 1 from above}
m
X
1+ skn0 = 1 k ∈ Enn0
k
≡ {simplifying}
X
skn0 = 0 k ∈ Enn0
k
≡ {using 0 ≤ snm ≤ 1 (96)}

skn0 = 0 k ∈ Enn0
⇒ {since n0 ∈ Enn0 }
sn0 n0 = 0
But this is a contradiction since we know sn0 n0 is fractional. Therefore snn cannot
be fractional and it cannot be 0.
snn = 1, n ∈ An0 (97)
Claim 5.2. snm = 0, n ∈ A p0 , m ∈ Dn , p0 = Pn0
Proof.
smm = 1, m ∈ An0
X
≡ {using smn = 1 (89)}
m
snm = 0, n ∈ Ap0 , m ∈ An0 , j ∈ Dn , p0 = Pn0

≡ {using snm = snk (95)}
snm = 0, n ∈ Ap0 , m ∈ Di , p0 = Pn0 (98)
66
Consider a point Q1 with sn0 n0 = 0:
/ (An0 ∪ Dn0 ∪ {n0 })

snm = sPnm , m ∈ (99)
sPnm
snm = , n ∈ An0 , j ∈ Dn (100)
1−t
snm = 0, n ∈ (Dn0 ∪ {n0 }), m ∈ Dn (101)
Claim 5.3. Point Q1 ∈ R2
Proof. We prove that point Q1 belongs to R2 by showing it satisfies the constraints (89),
(95) and (96).
For nodes that are not downstream or upstream of n0 , snm values are same as that
of point P . Therefore they satisfy the constraints since P belongs to R2 .
For the rest of the nodes:
For n ∈ An0 :
X
Proving (89) : smn = 1
m
{using snn = 1 (97)}

snn = 1, n ∈ An0
{using snm = 0 (98)}
smn = 0, n ∈ An0 , m ∈ An
≡ {summing over m}
X
smn = 1, n ∈ An0
m
Hence satisfied.
Proving (95) : snm = snk

{using snm = snk (95)}
sPnm = sPnk , n ∈ An0 , m ∈ Cn , k ∈ Dm
≡ {dividing by (1 − t) since t 6= 1 }
sPnm sP
= nk , n ∈ An0 , m ∈ Cn , k ∈ Dm
1−t 1−t
sPnm
≡ {using snm = (100)}
1−t
67
snm = snk , n ∈ An0 , m ∈ Cn , k ∈ Dm
Hence satisfied.
Proving (96) : 0 ≤ smn0 ≤ 1

X
{using smn = 1 (89)}
m
X
sPmn0 = 1, m ∈ An0 ∪ {n0 }
m
≡ {splitting sum}
X
sPmn0 + sPn0 n0 = 1, m ∈ An0
m
≡ {using sPn0 n0 = t}
X
sPmn0 = 1 − t, m ∈ An0
m
≡ {using sPmn0 ≥ 0 (96)}

0 ≤ sPmn0 ≤ 1 − t, m ∈ An0
≡ {dividing by (1 − t) since t 6= 1}
sPmn0
0≤ ≤ 1, m ∈ An0
1−t
sPnm
≡ {using snm = (100)}
1−t
0 ≤ smn0 ≤ 1, m ∈ An0
Hence satisfied.
For n ∈ Dn0 ∪ {n0 }:

X
m
X
m
X
sPmn0 = 1, m ∈ An0 ∪ {m0 }
m

sPkn0 + sPn0 n0 = 1, k = Pn0
≡ {using sPn0 n0 = t}
sPkn0 = 1 − t, k = Pn0
sPnm
≡ {using snm = (100)}
1−t
68
skn0 = 1, k = Pn0
≡ {using snm = 0 (101)}
X
smn = 1, n ∈ Dn0 ∪ {n0 }, m ∈ An
m
Hence satisfied.

{using snm = 0 (101)}
snm = 0 n ∈ Dn0 ∪ {n0 }, m ∈ Dn
≡
snm = snk n ∈ Dn0 ∪ {n0 }, m ∈ Dn , k ∈ Cn
Hence satisfied.
Proving (96) : 0 ≤ snm ≤ 1

{using snm = 0 (101)}
snm = 0 n ∈ Dn0 ∪ {n0 }, m ∈ Dn
Hence satisfied.
Therefore point Q1 ∈ R2 .
Similarly consider point Q2 with sn0 n0 = 1:
/ (An0 ∪ Dn0 ∪ {n0 })

snm = sPnm , m ∈ (102)
snm = 0, n ∈ An0 , m ∈ Dn (103)
sPnm
snm = , n ∈ (Dn0 ∪ {n0 }), m ∈ Dn ∪ {n} (104)
t
(95) and (96)
For nodes that are not downstream or upstream of n0 , snm values are same as that
of point P . Therefore they satisfy the constraints since P belongs to R2 .
For the rest of the nodes:
For n ∈ An0 :
X
m
69
{using snn = 1 (97)}
snn = 1, n ∈ An0
smn = 0, n ∈ An0 , m ∈ An
≡ {summing over m}
X
smn = 1, n ∈ An0
m
Hence satisfied.

{using snm = 0 (103)}
snm = 0 n ∈ An0 , m ∈ Dn
≡
snm = snk n ∈ An0 , m ∈ Dn , k ∈ Cn
Hence satisfied.
Proving (96) : 0 ≤ snm ≤ 1

{using snm = 0 (103)}
snm = 0 n ∈ An0 , m ∈ Dn
Hence satisfied.
For n ∈ Dn0 ∪ {n0 }:

X
m
X
m
X
sPmn = 1, m ∈ An ∪ {n}
m
≡ {splitting sum}
X X
sPmn + sPkn = 1, m ∈ Dn0 ∪ {n0 }, k ∈ An0
m k
X
≡ {using sPkn = 1 − t }
k
X
sPmn = t, m ∈ Dn0 ∪ {n0 }
m
≡ {dividing by t since t 6= 0 }
70
X sP
mn
= 1, m ∈ Dn0 ∪ {n0 }
m
t
sP
≡ {using snm = nm (104)}
X t
smn = 1, m ∈ Dn0 ∪ {n0 }
m
Hence satisfied.

{using snm = snk (95)}
sPnm = sPnk , m ∈ Cn , k ∈ Dm
sPnm sP
= nk , m ∈ Cn , k ∈ Dm
t t
sPnm
≡ {using snm = (104)}
t
snm = snk , m ∈ Cn , k ∈ Dm
Hence satisfied.
Proving (96) : 0 ≤ snm ≤ 1

X
m
X
sPmn = 1, m ∈ An ∪ {n}
m
≡ {splitting sum}
X X
sPmn + sPkn = 1, m ∈ Dn0 ∪ {n0 }, k ∈ An0
m k
X
≡ {using sPkn = 1 − t }
k
X
sPmn = t, m ∈ Dn0 ∪ {n0 }
m
{using 0 ≤ sPmn (96)}

0 ≤ sPmn ≤ t, m ∈ Dn0 ∪ {n0 }
sPmn
0≤ ≤ 1, m ∈ Dn0 ∪ {n0 }
t
sPnm
≡ {using snm = (104)}
t
71
0 ≤ smn ≤ 1, m ∈ Dn0 ∪ {n0 }
Hence satisfied.
Claim 5.5. P is a linear combination of points Q1 and Q2 i.e. P = (1 − t)Q1 + tQ2
/ (An0 ∪ Dn0 ∪ {n0 }):

Proof. For m ∈
{using sPnm = sQ P Q2
nm (99) and snm = snm (102)}
1
sPnm = sQ Q2
nm = snm
1
⇒
sPnm = (1 − t)sQ Q2
nm + t ∗ snm
1
For n ∈ An0 , m ∈ Dn :
sPnm
sQ
nm =
1
{100}
1−t
sQ
nm = 0
2
{103}
⇒
nm + t ∗ snm
1
For n ∈ Dn0 , m ∈ Dn :
sQ
nm = 0
1
{101}
sPnm
sQ
nm =
2
{104}
t
⇒
nm + t ∗ snm
1
Therefore P is a linear combination of points Q1 and Q2 .
Since any general point P with a fractional component can be expressed as linear
combination of two other points in the set R2 , it implies that such a point P cannot be a
corner point and therefore set R2 is tight.
This concludes the discussion on the three improvements made to the initial ILP
model. Experimental results of the performance of the model after each improvement is
presented in Section 7.4. The model in its entirety after the inclusion of all the network
components and these improvements is described in Appendix I. Although we have shown
the tightness of various subsets of the improved model, the overall set of constraints of
72
the model is still not tight. As such, there remains room for further improvements to
the model. In Chapter 8 we describe an initial attempt at an alternative approach to
the problem. Instead of using node variables sij to partition the primary and secondary
network, purely edge based variables are used.
7.4 Computational Results

The three pipe cost/ESR cost/ESR allocation improvements were applied sequentially to
the initial model (model 1) to give model-2/model-3/model-4 respectively. These four
models were tested over eight different networks of varying sizes in order to test their
performance and scalability:
• Real World Networks: Three of the networks, Khardi, Shahpur and Mokhada are
real life networks from Maharashtra state in India. These regions consist of tribal
villages that regularly face extreme water stress during summer months and as a
result have to be provided water using tankers.
• Synthetic Networks: The other five networks are artificially created to test the
performance of the models across different network sizes (10 to 200). Each of them
is a randomly generated branched network. Ranges for the node and link properties
are as follows:
– Number of children nodes: 1 to 5,

– Elevation (in metres): 100 to 300,
– Demand (in litres per second): 0.01 to 5,
– Length of links (in metres): 500 to 5000.
For all four models, the problem statement remains the same, to optimize the total
pipe and ESR cost of the network. The number of binary and continuous variables scale
with the size of the network. Since all four models solve the problem optimally, the
final capital cost of the pipes and ESRs is the same. The performance of each model is
measured in terms of three metrics: the total time taken in seconds, the size of the branch
and bound tree and the objective value of the LP relaxation. Table 7.1 summarizes the
performance of the models. We observe that for each of the eight networks, the time taken
improves with each model, resulting in model-4 providing the best performance. Typically
the time taken scales with the size of the network. However, this need not always be the
case. For example, although gen50 has more nodes (50 nodes) than Mokhada (37 nodes),
it is solved in lesser amount of time. This is because apart from the number of nodes
being a factor, the network configuration also matters while solving the model.
73
Table 7.1: Performance of the various models on the eight networks.
Binary Continuous Objective
Network Nodes Metric Model-1 Model-2 Model-3 Model-4
Variables Variables (Rs)
Time(s) 1.71 0.96 0.47 0.32

gen10 10 228 527 2.18E7 B&B Tree Size 8 14 2 10
LP Obj. (Rs) 7.89E6 7.89E6 1.02E7 1.02E7
Time(s) 0.74 0.36 0.31 0.24
Khardi 11 262 584 4.48E7 B&B Tree Size 2 0 0 0
LP Obj. (Rs) 1.14E07 1.16E07 2.90E07 2.90E07
Time(s) 11.66 3.36 1.90 0.72
Shahpur 21 712 1154 4.54E7 B&B Tree Size 148 27 4 4
LP Obj. (Rs) 2.00E7 2.02E7 2.69E7 2.69E7
Time(s) 28.78 7.91 3.48 2.02
Mokhada 37 1848 2066 4.94E7 B&B Tree Size 965 188 68 30
LP Obj. (Rs) 2.16E7 2.16E7 3.05E7 3.05E7
Time(s) 373.49 39.31 2.02 1.27
gen50 50 3148 2807 9.82E7 B&B Tree Size 15228 1240 8 6
LP Obj. (Rs) 4.00E7 4.00E7 5.58E7 5.58E7
Time(s) 197.89 129.75 9.73 4.18
gen100 100 11298 5657 2.47E8 B&B Tree Size 1735 1958 120 32
LP Obj. (Rs) 9.34E7 9.34E7 1.27E8 1.27E8
Time(s) 2582.35 887.68 18.67 5.25
gen150 150 24448 8507 3.48E8 B&B Tree Size 22401 15498 148 8
LP Obj. (Rs) 8.50E7 8.53E7 1.35E8 1.35E8
Time(s) timeout* timeout* 523.97 69.80
gen200 200 42598 11357 4.55E8 B&B Tree Size - - 5034 858
LP Obj. (Rs) 1.12E8 1.12E8 1.83E8 1.83E8
*timed out after running for 24 hours
74
Chapter 8
Edge Based Model
Determining the ESR configuration involves two components, partitioning the network
into primary and secondary networks and determining the demand each ESR has to
serve. In our model, the allocation of nodes to ESRs is done using the node based binary
variables sij which is true if the ESR at the ith node serves the j th node. These variables
therefore explicitly determine the demand each ESR serves. An alternative approach to
this node based representation of the network is to have an edge based representation.
Here instead of the focus being which ESR serves which node, the focus is on which pipes
in the network are part of the primary network and which pipes are part of the secondary
network.
8.1 Model Details

Consider a tree network of N E edges:
Parameters:
Ci = Set of pipes that are immediately downstream of pipe i, i = 1, . . . , NE.
Ui = Set of pipes that are upstream of pipe i, i = 1, . . . , NE.
Di = Set of pipes that are downstream of pipe i, i = 1, . . . , NE.
DS = Set of pipes that are immediately downstream of the source.
Variables:
fi = 1 if ith edge belongs to the primary network and = 0 if ith edge belongs to the
secondary network, i = 1, . . . , e
The primary network connects the source to the ESRs, and the secondary network
connects the ESRs to downstream nodes. Therefore pipes starting from the source must
75
belong to the primary network. Also, secondary pipes must be downstream of the pri-
mary pipes. And once a pipe is secondary, then any pipes downstream can no longer
be primary. We can use the following set of constraints to describe the set S3 of valid
network configurations:
fi = 1, i ∈ DS, (105)
fj ≤ fi , i = 1, . . . , N E, j ∈ Ci , (106)

fi ∈ 0, 1 , i = 1, . . . , N E. (107)
8.2 Tightness Proof

We show that the linear relaxation of S3 is tight, i.e. it does not contain any corner points
with non-integral components.
Proposition 6. The linear relaxation of S3 is tight.
Proof. Let the linear relaxation of set S3 be R3 . Instead of constraint (107) we will have
the following constraint:
0 ≤ fi ≤ 1, i = 1, . . . , N E. (108)
We will show that R3 is tight by showing any point P , with a non-integer component
can be expressed as a linear combination of two distinct points from R3 .
Consider a point P ∈ R3 with 0 < fi = t < 1 for some i0 . Let i0 be the first such edge in
the path from source.
Claim 6.1. fi = 1, i ∈ Ui0
Proof. fi cannot be fractional since i0 is the first such edge from source by definition. If
fi = 0, then by (106) for all its downstream edges j, fi = 0. But i0 is downstream of i
and fi0 = t 6= 0. Therefore fi cannot be fractional and it cannot be 0.
fi = 1, i ∈ Ui0 . (109)
Consider a point Q1 with fi0 = 0:
/ (Di0 ∪ {i0 }),

fi = fiP , i ∈ (110)
fi = 0, i ∈ (Di0 ∪ {i0 }). (111)
76
Proof. For all the edges not downstream of i0 , constraints (105), (106) and (108) are
satisfied since the values are same as point P and P ∈ R3 . Setting fi = 0 for all
downstream i also maintains the constraints trivially. Therefore point Q ∈ R3 .
Similarly consider point Q2 with fi0 = 1:
/ (Di0 ∪ {i0 }),

fi = fiP , i ∈ (112)
fiP
fi = , i ∈ (Di0 ∪ {i0 }). (113)
t
(106) and (108). For edges that are not downstream of i0 , fi values are same as that of
point P . Therefore they satisfy the constraints since P ∈ R3 . For the rest of the edges:
For i ∈ (Di0 ∪ {i0 }): (105) is trivially true since i0 (and its downstream edges)
cannot be connected to the source since for point P , fi 6= 0.
Proving (106) : fj ≤ fi
{using fjP ≤ fiP (106)}
fjP ≤ fiP , i ∈ (Di0 ∪ {i0 }), j ∈ Ci
fjP fP
≤ i , i ∈ (Di0 ∪ {i0 }), j ∈ Ci
t t
fiP
≡ {using fi = (113)}
t
fj ≤ fi , i ∈ (Di0 ∪ {i0 }), j ∈ Ci
Hence satisfied.
Proving (108) : 0 ≤ fi ≤ 1
{using fiP ≤ fiP0 (106) and 0 ≤ fiP (108)}
0 ≤ fiP ≤ fiP0 i ∈ (Di0 ∪ {i0 })
≡ {using fiP = t }
0 ≤ fiP ≤ t i ∈ (Di0 ∪ {i0 })
fiP
0≤ ≤1 i ∈ (Di0 ∪ {i0 })
t
fiP
≡ {using fi = (113)}
t
0 ≤ fi ≤ 1 i ∈ (Di0 ∪ {i0 })
77
Hence satisfied.
Claim 6.4. P is a linear combination of points Q1 and Q2 i.e. P = (1 − t)Q1 + tQ2
/ (Di0 ∪ {i0 }):

Proof. For i ∈
fiP = fiQ1 = fiQ2 {110, 112}

⇒
fiP = (1 − t)fiQ1 + t ∗ fiQ2
For i ∈ (Di0 ∪ {i0 }):
fiQ1 = 0 {111}
fiP
fiQ2 = {113}
t
⇒
fiP = (1 − t)fiQ1 + t ∗ fiQ2
Therefore P is a linear combination of points Q1 and Q2
Since any general point P with a fractional component can be expressed as a linear
combination of two other points in the set R3 , it implies that such a point P cannot be a
corner point and therefore relaxation R3 is tight.
8.3 Computational Results
Table 8.1: Performance of the edge based model.

Network Nodes Model-1 Model-2 Model-3 Model-4 Edge Model
gen10 10 1.71 0.96 0.47 0.32 0.40
Khardi 11 0.74 0.36 0.31 0.24 0.39
Shahpur 21 11.66 3.36 1.90 0.72 0.91
Mokhada 37 28.78 7.91 3.48 2.02 3.03
gen50 50 373.49 39.31 2.02 1.27 1.86
gen100 100 197.89 129.75 9.73 4.18 4.97
gen150 150 2582.35 887.68 18.67 5.25 16.14
gen200 200 timeout* timeout* 523.97 69.80 100.84
*timed out after running for 24 hours
78
Table 8.1 displays the performance of the edge based model in comparison to the
four models from Chapter 7 in terms of time taken in seconds. The performance of the
edge based model is between that of model-3 and model-4. Although we prove that the
LP relaxation of the set of constraints described by S3 is tight, the LP relaxation objective
for the overall model is worse. This is due to changes in other constraints of the model.
Computing the demand dn that an ESR at node n serves now becomes more complicated
since in this model only edge based variables are considered. Instead of the linear equation
for dn in the original model (38), we now have the following equation:
X
dn = DEm ∗ fi ∗ (1 − fj ), n = 1, . . . , N N i = In , j = On = Im . (114)
j∈Di
This equation is non-linear since it contains the product of two variables fi and fj . Since
both are binary the product term can be linearized but this introduces many constraints
which deteriorates the performance. Therefore the model implemented in the JalTantra
system is model-4. Details of the JalTantra system are provided in the next chapter.
79
80
Chapter 9
JalTantra System Description
In this chapter we describe the system JalTantra, that we created for the design and
optimization of piped water networks. The aim of the system is to be optimal and fast
while at the same time providing an interface that is simple and intuitive to use. We
discuss the main features of the system and highlight how it achieves the objectives we
laid out in Section 1.1. Details regarding how to use the system can be found in Appendix
II.
9.1 First Iteration: A Desktop JAVA Application
Figure 9.1: General Tab of JalTantra desktop Java application
Government engineers tasked with design of water networks in India work on sys-
tems with operating systems ranging from Windows XP to Windows 10. We wanted to
81
develop the system using cross-platform technology that would not only work on the range
of machines currently being used by real world practitioners but also be future proof. To
that end, the first version of JalTantra was developed as a JAVA [35] desktop application.
The application provided a user interface through which the user could input details
of the network as seen in figure 9.1. Input could also be provided via XML files. This
version only solved the pipe diameter selection problem described in Chapter 4. Once the
network was entered, the user could start the optimization and the final results could be
seen on a separate result tab as seen in figure 9.2. For the optimization we first used the
linear solver lpsolve 5.5 [9]. This was subsequently replaced with a faster linear solver
library GLPK 4.55 [26]. For both lpsolve and GLPK, Java ILP 1.2a [36] was used as the
Java interface to the solver libraries.
Figure 9.2: Results Tab of JalTantra desktop Java application
Once developed, feedback on JalTantra was sought from designers from the gov-
ernment offices of MJP. We did this by one on one interactions as well as holding multiple
tutorial sessions where the engineers could get a hands on experience with the system.
During these tutorials, we found that JAVA was not installed on these machines more
often than not. Even when installed, sometimes the PATH variables would not be set
correctly and thus the machine would not be able to launch JalTantra. We had to fre-
quently intervene and help the engineers with the initial setup due to these issues. We
realised issues could also arise when JalTantra or JAVA was updated in the future and a
reinstallation would be required by the user. We also wanted to include a GIS based inte-
gration in future versions of JalTantra, which would significantly ease in input of network
82
details. With the inclusion of more network components like tanks, pumps and valves,
some of the very old machines might have a hard time running the optimization. With
these things in mind, we decided to migrate JalTantra to a web system.
Figure 9.3: JalTantra Web System
9.2 JalTantra 2.0: A Web System

Given the installation, maintenance and scalability issues for a desktop application, we de-
cided to instead develop JalTantra as a web application as seen in figure 9.3. Now all that
would be required from the user is a simple web browser. Any updates to the system could
be pushed without disrupting the user experience. A web application allows JalTantra
to be used on any system. The system is available at http://www.cse.iitb.ac.in/jaltantra
. It includes links to usage instructions, a video tutorial and sample input/output files.
The system can also be downloaded and run on a local server for offline use. The local
server version requires JAVA 7 [35].
9.3 System Architecture

JalTantra is a web application with three principal components as shown in figure 9.4:
Client Interface: The client interface houses the logic used to interact with the
user. Its built using javascript libraries jQuery [37] and w2ui [72]. The dagre [17] javascript
library was used to generate the spatial coordinates for the network when saving the
network as an EPANET file. Once the user has provided all the network details after a
preliminary validation step, the network is converted into JSON objects and a request is
made to the web server.
83
Figure 9.4: JalTantra System Architecture
Web Servlet: A JAVA web servlet acts as the intermediary between the web
interface and the optimization engine. Upon receiving a web request, it unpacks the
JSON string objects and converts them into JAVA objects and then forwards these to the
optimization engine. Upon receiving the results from the optimization engine, it converts
the results into JSON objects and sends a response to the web client.
Optimization Engine: The optimization engine houses the core logic of the
system. It is here where the provided network is validated and then the optimization
problem is generated as an Integer Linear Program (ILP). This program is then provided
to a third party ILP solver. Since a lot more constraints and variables were added with
the ESR integration, instead of using GLPK, we moved on to a faster solver CBC [22]. We
used the Google OR Tools [28] JAVA interface to call the CBC solver. The abstraction
provided by the Google OR tools interface allows us to use more powerful commercial
solvers in the future without any code rewrite.
9.4 Data Handling
One of the objectives that we had set out when designing JalTantra was that it should
be easy to use in terms of input of data, since that is one of the most tedious steps in
the design process. Additionally there should be interoperability between JalTantra and
legacy systems used by engineers to ease their transition to JalTantra. Data input to
JalTantra can be entered manually in the various tabs discussed above or via importing
84
files in various formats. Importing a file will populate all the fields in the tabs of the
system.
• BRANCH Files: .bra file format used by BRANCH. Users of BRANCH software
can easily test JalTantra using their existing files.
• XML Files: .xml file format. Standard XML format to allow easy input from future
third party sources.
• Excel Files: .xls file format. Suited for users having data already present in Excel
files.
Figure 9.5: EPANET for Mokhada Network
The output of the optimization can be saved as an Excel File. Another option that
is included is the ability to export the network as an EPANET file. This is useful since
EPANET is the de-facto software used for running water networks simulations. Previously
it would be a tedious process to transfer the output of JalTantra or BRANCH and create
85
the EPANET network manually. Figure 9.5 shows the EPANET file generated for the
Mokhada network.
9.5 GIS Integration

As mentioned earlier (and can be seen in the figures above), to describe the network we
need to provide elevation data for nodes as well as the lengths of the links connecting them.
These values are measured using physical surveys at location to ensure accuracy before
doing the final design. But for earlier prototype designs to gauge feasibility of the design
GIS data is used. This data is looked up and then entered manually. This can be a very
tedious process, especially for link distances since the link must typically be manually
drawn along the road network. As part of our web system we have integrated google
map based GIS [27] which allows the user to add nodes on the map. Links between
the nodes can be simply added using the google directions service without having to
manually enter the entire path. The tool also allows to view the elevation profile of the
paths generated. This is then used to add dummy nodes along the path at points of high
elevation. Information like elevations and distances can then be extracted directly into
the node/pipe information screens. A sample network created using the GIS tool is shown
in figure 9.6.
Figure 9.6: GIS Tool in JalTantra
86
Chapter 10
Conclusion and Future Work
10.1 Conclusion
With this thesis, our objective was to create a system that will help government engineers
and other users in the design and optimization of piped water networks. We looked at the
cost optimization of rural drinking water schemes in particular. These schemes consist
of several network components like pipes, tanks, pumps and valves. We motivated the
importance of considering all these components while optimizing as opposed to just the
pipe diameters. We presented an ILP model that was used to solve the problem.
Although optimal, the model took a significant amount of time for larger networks,
45 minutes for a network with 150 nodes. We then described a series of three improvements
of the model. For each improvement we proved that the improved model is tighter than
the initial model. We then presented the performance results of the three improved models
along with the initial model over eight networks of various sizes. The 150 node network
now takes only 5 seconds to solve. This enables practitioners to consider greater number
of iterations of the design for large networks, since each iteration can be optimized in a
matter of seconds.
We have implemented our solution in a water network design web system JalTantra,
available publicly at http://www.cse.iitb.ac.in/jaltantra . JalTantra also has GIS integra-
tion for ease of adding network details. It handles legacy file formats such as BRANCH
and Excel files. This helps users to transition to JalTantra smoothly. After the optimiza-
tion, it can also output the network details as an EPANET file which is used to simulate
and validate the network.
We held several tutorial and demo sessions with government engineers from the
MJP and received positive feedback. MJP has officially adopted it as one of the software
packages to be used in the design of water supply schemes. MEETRA which is responsible
for the training of MJP engineers, has integrated JalTantra into its curriculum. Addition-
ally, details of the JalTantra system has been included in a compendium titled ”Improving
87
the performance of rural water supply and sanitation sector in Maharashtra”.
10.2 Future Work

In the present work we have looked at the design and optimization of piped water networks
and in particular rural networks. Some of the assumptions include branched network, fixed
demands, minimizing capital and operational cost. Each of these assumptions could be
relaxed to generalize the problem further, leading to future work in various directions:
Looped Networks: Although rural networks are branched, urban and semi-urban net-
works are typically looped. A natural extension of the current work would be extend the
model to include looped networks.
Alternative Objective Criteria: The introduction of operational cost opens up inter-
esting possibilities in determining the objective function. Currently we use the standard
technique of considering the present value of the entire operational cost and simply adding
it to the capital cost. One line of future work would lie in considering alternative objective
functions. In particular, because operational cost is often the cause of schemes becoming
obsolete, it might be desirable to consider only the operational cost as the minimization
objective and constrain the capital cost so that it does not exceed current government
norms.
Scheduling and Operation: Currently the demands in the network are assumed to be
fixed and are simultaneously satisfied. More complicated and dynamic demand patterns
could be studied. By including operational considerations the demands need not be
simultaneously satisfied but could be staggered throughout the day.
EPANET Integration: Currently once the network components have been determined
by JalTantra, the network details are entered into EPANET to verify the solution. The
EPANET hydraulic library could be integrated into JalTantra to ease this process and
provide the user with a unified experience.
Integrating more design steps: We started with just pipe diameter selection and
iteratively automated more steps from the design process and included them in JalTantra.
This process could continue further. For example, currently the demands are calculated
using population forecasting and then fed into the system. This could be integrated into
JalTantra itself, while also leveraging GIS technology to map the demand more accurately.
Cost Allocation: A common source of scheme failure is the refusal of payments by
users due to a mismatch in the perceived benefits and payment demanded. Currently all
users are assumed equal, when in reality there is great variance in the quality of service
received in the case of multi village schemes. Analysing this disparity and allocating cost
accordingly is an interesting problem in the design of multi village piped water schemes.
88
Appendices
Appendix I
Complete ILP Model
Drinking water distribution networks consist of various components. To optimize the

cost of such networks, several inputs must be considered, and for each component several
parameters must be determined. We first explicitly formulate the problem that we are
attempting to solve and then provide details of the ILP model used to solve the problem.
I.1 Problem Formulation

Inputs:
• General: primary/secondary supply hours, minimum/ maximum headloss per km,

maximum water speed
• Source node: head
• Node: elevation, water demand, minimum pressure requirement
• Link: start/end node, length
• Existing Pipes: start/end node, length, diameter, parallel allowed, roughness
• Commercial Pipes: diameter, roughness, cost per unit length
• Tanks: maximum tank heights, tank capacity factor, nodes that must/must not
have tanks, capital cost table
• Pumps: minimum pump size, efficiency, design lifetime, capital/energy cost, dis-
count/interest rate, pipes that cannot have pumps
• Valves: location, pressure rating
89
Outputs:
• Length and diameter of pipe segments for each link
• Partitioning the set of links into primary and secondary network
• Location, height and size of Tanks
• Set of nodes being served by each Tank
• Location and power of Pumps
Objective:
• Minimize total capital cost (pipe + tank + pump) and total energy cost (pump)
Constraints:
• Pressure at each node must be at least the minimum pressure specified
• Water demand must be met at each node
I.2 Model Details

The pipe diameter selection in the model is represented by the continuous variable lij
which represents the length of the j th pipe diameter component of the ith link in the
network. This determines the capital cost of the pipes. The tank allocation is represented
by the binary variable snm which is one if the tank at the nth node in the network provides
water to the mth node in the network. The choice of tank allocation variables fixes the
total demand that each tank serves i.e. the variable dn . This in turn determines the
capital cost of the tanks. Apart from the cost considerations, each node n must also have
its minimum pressure constraint satisfied. The head at each node, hn is dependent on the
headloss hli in the links of the network. This headloss depends on the pipe variables lij and
the tank variables snm mentioned earlier. In addition, the introduction of pumps/valves
increases/decreases the headloss respectively. The details of the parameters, variables,
objective function and constraints of the model are as follows:
Parameters:
• N L: Number of links in the network
• N P : Number of commercial pipe diameters
• Dj : Diameter of j th commercial pipe diameter
90
• Cj : Cost per unit length of j th commercial pipe diameter
• N N : Number of nodes in the network
• N E: Number of rows in the tank cost table
• Bk : Base cost of the k th row of the tank cost table
• U Nk : Unit cost of the k th row of the tank cost table
• U Pk : Upper limit capacity for the k th row of the tank cost table
• LOk : Lower limit capacity for the k th row of the tank cost table
• CP : Capital cost of pumps per unit kW
• EP : Energy cost of pumps per unit kWh
• DF : Discount factor for the energy cost over the entire scheme lifetime
• P H: Number of hours of water supply in the primary network
• SH: Number of hours of water supply in the secondary network
• Y : Lifetime of scheme in years
• IN F R: Inflation rate
• IN T R: Interest rate
• Li : Length of the ith link
• P Rn : Minimum pressure required at node n
• En : Elevation of the nth node
• DEn : Water demand of the nth node
• DE: The total water demand of the network
• V Hi : Head reduction by valve in ith link
• HLpij : Headloss for the j th diameter of the ith link, if i is part of the primary network
• HLsij : Headloss for the j th diameter of the ith link, if i is part of the secondary
network
• F Lpi : Flow in ith link if i is part of the primary network
91
• F Lsi : Flow in ith link if i is part of the secondary network
• Rj : Roughness of j th commercial pipe diameter
• Tmin : Minimum tank height allowed
• Tmax : Maximum tank height allowed
• ρ: Density of water
• g: Acceleration due to gravity
• η: Efficiency of pump
• P Pmin : Minimum pump power allowed
• P Pmax : Maximum pump power allowed
• An : Set of nodes that are ancestors of node n
• Dn : Set of nodes that are descendants of node n
• Cn : Set of child nodes of node n
• Pn : Parent node of node n
• In : Incoming link for node n
• On : Set of outgoing links from node n
• lij : Length of the j th pipe component of the ith link
p
• lij : Length of the j th pipe component of the ith link, if link i is part of the primary
network
s
• lij : Length of the j th pipe component of the ith link, if link i is part of the secondary
network
• hli : Total headloss across link i
• dn : Total demand served by tank at node n
• znk : Total demand served by tank at node n, if costed by the k th row of the tank
cost table
92
• pi : Power of pump installed at link i
• ppi : Power of pump installed at link i, if link i is part of primary network
• psi : Power of pump installed at link i, if link i is part of secondary network
• phi : Head provided by pump at link i
• hn : Water head at node n
• tn : Height of tank at node n
• h0 ni : Effective head provided to link i by its starting node n
Binary Variables:
• enk : 1 if tank at nth node is costed by the k th row of tank cost table, 0 otherwise
• fi : 1 if link i is part of the primary network, 0 if part of the secondary network
• esni : 1 if source of water for link i is its immediate upstream node n, 0 otherwise
• snm : 1 if tank at node n is source for node m, 0 otherwise
• pei : 1 if a pump is installed at link i, 0 otherwise
Objective Function: The objective function is simply the sum of capital cost of the
pipes, tanks, pumps and valves used in the network. In addition, we also have the
operational cost of the pumps. This operational cost is computed as the present value of
the total cost over the scheme lifetime.
NL X
X NP NL X
X NP
O(.) = Cij (Dij )lij + Li Cij (Dij )pij
NN X
X NE
+ enk ∗ (Bk + U Nk ∗ (dn − LOk ))
n=1 k=1
NL NL NL
!
X X X
+ CP ∗ pi + EP ∗ DF ∗ P H ∗ ppi + SH ∗ psi ,
i=1 i=1 i=1
Y n−1
X 1 + IN F R
where DF = .
n=1
1 + IN T R
93
Constraints:
• The length of each link segment lij , is the sum of the primary and secondary com-
p s
ponents, i.e. lij and lij respectively:
p s
lij = lij + lij , i = 1, . . . , N L, j = 1, . . . , N P.
p s
• For a given link i, either all lij are 0 or all lij are 0, depending on the value of fi .
And the sum of the non-zero components must equal the length of the link Li .
NP
X p
lij = Li fi , i = 1, . . . , N L,
j=1
NP
X
s
lij = Li (1 − fi ), i = 1, . . . , N L.
j=1
• The pressure at each node must exceed the minimum pressure required:
P Rn ≤ hn − (En + tn ), n = 1, . . . , N N .
• Across every link i there is headloss hli . This headloss depends on the flow, length
and diameter of the pipe chosen. We use the Hazen-Williams equation [74] to
calculate the headloss. The headloss across a link also depends on the pump and
valve installed across it, if any. The valves are input parameters to the model since
they are manually fixed. The constraints related to the pump head phi are described
further below. The flow through the link depends on whether the link is part of the
primary or secondary network:
NP
X
hli = (HLpij lij
p
+ HLsij lij
s
) − phi + V Hi , i = 1, . . . , N L,
j=1
1.852
F Lpi

10.68 ∗ Rj
HLpij = , i = 1, . . . , N L, j = 1, . . . , N P,
Dj4.87
s 1.852
FL
10.68 ∗ Rji
HLsij = , i = 1, . . . , N L, j = 1, . . . , N P,
Dj4.87
PH
F Lsi = F Lpi ∗ , i = 1, . . . , N L.
SH
• The head hn at each node n is calculated by the effective head h0mi provided by
its parent node m and the headloss hli across the link connecting two nodes. The
effective head in turn depends on whether the link i has the tank at the starting
node m as its source. This is represented by the binary variable esmi :
hn = h0mi − hli , n = 1, . . . , N N, m = Pn , i = In ,
94
h0mi = (tm + Em ) ∗ esmi + hm ∗ (1 − esmi ), m = 1, . . . , N N, i ∈ Om ,
esmi = smm ∗ (1 − fi ), m = 1, . . . , N N, i ∈ Om .
• Next, we look at the constraints related to the tank allocation. The first tank
constraint is to ensure that every tank height is between parameters Tmin and Tmax .
Tmin ≤ tn ≤ Tmax .
• We then look at the constraints that model allocation of demand nodes to tanks.
snm is 1 if tank at node n serves the demand of node m. A node n serves its child
m if and only if it serves all the nodes downstream of m:
snm = snk , n = 1, . . . , N N, m ∈ Cn , k ∈ Dm .
• For every node n, only one upstream node m can serve its demand.
X
smn = 1, n = 1, . . . , N N .
m∈An ∪{n}
• The total demand dn served by node n is the sum of the demands of the downstream
nodes that it serves i.e. all m such that snm = 1.
X
dn = snm ∗ DEm , n = 1, . . . , N N .
m∈Dn ∪{n}
• For a node n, its incoming pipe i will have primary flow only if the node serves
itself.
fi = snn , n = 1, . . . , N N, i = In .
• Next, we have the constraints that relate the demand that a tank serves to its cost
variables enk . Note that we require znk in our objective function to replace the non
linear term enk × dn . The following two inequalities of the model provide the bounds
for znk in terms of enk and the minimum(LOk ) and maximum(U Pk ) capacities for
each row of the cost table:
LOk enk ≤ znk , n = 1, . . . , N N, k = 1, . . . , N E,

znk ≤ U Pk enk , n = 1, . . . , N N, k = 1, . . . , N E.
• Since every tank can be costed using exactly one row of the table, the sum of enk
for a given n must be 1:
NE
X
enk = 1, n = 1, . . . , N N .
k=1
95
• Next, we have a similar equation but this time related to the variable znk . The sum
of all znk values for a given tank must equal dn :
NE
X
znk = dn , n = 1, . . . , N N.
k=1
• Next, we look at constraints related to pumps. The pump power pi relates to the
pump head phi in the following way:
pi = ppi + psi , i = 1, . . . , N L,
(ρ ∗ g ∗ F Lpi ∗ phi )
ppi = ∗ fi , i = 1, . . . , N L,
η
(ρ ∗ g ∗ F Lsi ∗ phi )
psi = ∗ (1 − fi ), i = 1, . . . , N L .
η
• Finally, the pump power for each pump must lie between minimum and maximum
allowed pump power. This is implemented using the binary variable pei .
P Pmin ∗ pei ≤ pi ≤ P Pmax ∗ pei , i = 1, . . . , N L .
96
Appendix II
JalTantra Usage Details
The web interface of JalTantra is split into two panels as can be seen in Figure 9.3. The
sidebar panel on the left enables the user to switch through the various tabs of the system.
Clicking on any of them fills the main panel on the right with the relevant content. We
go through each of the tabs available and briefly discuss their functionality below. For
each tab we list the inputs that the user may provide. The format for each input is:
{Name of the Input}:{Variable Type} {Unit of Input} {Mandatory?} {Definition}
Figure II.1: General Tab of JalTantra
General Tab: Figure II.1 displays the content of the general tab. As the name
suggests, this tab is used to enter the general information about the network. The fields
to be entered are:
• Name of Project: Text (Your Project Name)
97
• Minimum Node Pressure: Double (metre) (The default minimum pressure that must
be maintained at all nodes)
• Default Pipe Roughness: Double (The default pipe roughness that is used to calcu-
late headloss in the pipes)
• Minimum Headloss per KM: Double (metre) (The minimum headloss per km that
is allowed in each pipe)
• Maximum Headloss per KM: Double (metre) (The maximum headloss per km that
is allowed in each pipe)
• Maximum Speed of Water: Double (metre per second) (not mandatory, default:no
constraint) (Maximum speed of water in metres per second that is allowed in a pipe)
• Maximum Pressure in Pipe: Double (metre) (not mandatory, default:no constraint)

(Maximum pressure of water in metres that should exist in a pipe. Note that this
constraint is not strictly enforced, but a warning is provided in the results if pressure
is exceeded)
• Number of Supply Hours: Double (Number of hours in a day that water is supplied
for. For example if supply hours is 12 it corresponds to a peak factor of 2)
• Source Node ID: Integer (The unique node id of the source)
• Source Node Name: String (The name of the source node)
• Source Head: Double (metre) (The constant water head provided by the source)
• Source Elevation: Double (metre) (The elevation of the source)
Figure II.2: Nodes Tab of JalTantra
Nodes Tab: Figure II.2 displays the content of the node tab. This tab is used to
enter the information about the nodes in the network. The fields to be entered are:
98
• NodeID: Integer (unique nodeID of your node)
• Node Name: String (Name of your node)
• Elevation: Double (metre) (elevation of your node)
• Demand: Double (litres per second) (not mandatory, default:0) (demand of your
node)
• Min. Pressure: Double (metre) (not mandatory, default: from general tab) (mini-
mum pressure that needs to maintained at the node)
• Add New: (Add extra row corresponding to one node)
• Delete: (Remove selected rows)
Figure II.3: Pipes Tab of JalTantra
Pipes Tab: Figure II.3 displays the content of the pipe tab. This tab is used to
enter the information about the pipes in the network. The fields to be entered are:
• PipeID: Integer (unique pipeID of your pipe)
• Start Node: Integer (nodeID of the node at the start of your pipe)
• End Node: Integer (nodeID of the node at the end of your pipe)
• Length: Double (metre) (length of your pipe)
• Diameter: Integer (millimeter) (not mandatory, default:to be calculated) (diameter

of your pipe)
• Roughness: Double (not mandatory, default:from general tab) (roughness of pipe

that is used to calculate the headloss in the pipe)
• Parallel Allowed: Boolean (not mandatory, default: false) (If a new pipe is allowed
to be placed in parallel to an existing pipe.)
99
• Add New: (Add extra row corresponding to one pipe)
Figure II.4: Commercial Pipes Tab of JalTantra
Commercial Pipes Tab: Figure II.4 displays the content of the Commercial
Pipes tab. This tab is used to enter the information about the discrete set of commercially
available pipe diameters in the network. The fields to be entered are:
• Diameter: Integer (millimeter) (unique diameter of the commercial pipe)
• Roughness: Double (not mandatory, default:from general tab) (Roughness of the

commercial pipe)
• Cost: Double (Rs per metre) (cost per metre of the commercial pipe)
• Add New: (Add extra row corresponding to one commercial pipe)
ESR Tab: Figure II.5 displays the content of the ESR tab. This tab is used to
enter the information about the ESRs in the network. The fields to be entered are:
• Secondary Network Supply Hours : Double (Number of hours in day that an ESR
provides water to its secondary network)
• ESR Capacity Factor: Double (Size of ESR in relation to the daily demand it serves.
For e.g. a value of 0.5 means that the ESR capacity is half the daily demand)
100
• Maximum ESR Height: Double (metre) (not mandatory, default:no constraint)
(Maximum height of ESR in metres)
• Allow ESRs at zero demand nodes: Boolean (not mandatory, default:false) (Allow
ESRs to placed at nodes with zero demand. Note that if zero demand nodes are
not allowed optimization will be significantly faster)
• Nodes with ESRs: (not mandatory, default:no constraint) (List of Nodes that must
have ESRs)
• Nodes without ESRs: (not mandatory, default:no constraint) (List of Nodes that
must not have ESRs)
ESR Cost Tab: Within the ESR Tab, there is a separate ESR cost tab as shown
in Figure II.6. This tab is used to enter the information about the cost of ESRs. The
fields to be entered are:
• Minimum Capacity: Double (litre) (default: max capacity of previous row) (Mini-
mum capacity of the row in the ESR cost table)
• Maximum Capacity: Double (litre) (Maximum capacity of the row in the ESR cost
table)
• Base Cost: Double (Rs) (default: calculated from previous row) (base cost of ESR
having capacity between the minimum and maximum capacity)
• Unit Cost: Double (Rs per litre) (unit cost of ESR having capacity between the
minimum and maximum capacity)
• Add New: (Add extra row for the ESR cost table)
Figure II.5: ESR Tab of JalTantra
101
Figure II.6: ESR cost Tab of JalTantra
Pump Tab: Figure II.7 displays the content of the Pump tab. This tab is used
to enter the information about the pumps in the network. The fields to be entered are:
• Minimum Pump Size : Double (kW) (Size of Minimum Pump in kW that can be
installed)
• Pump Efficiency: Double (Efficiency of pump expressed as a %)
• Capital Cost per kW: Double (Rs) (Capital cost of the pump per kW installed
capacity)
• Energy Cost per kWh: Double (Rs) (Energy cost per kWh energy consumed)
• Design Lifetime: Integer (Number of years for which pumps will be operational)
• Discount Rate: Double (not mandatory, default: 0) (Discount rate is the interest
rate expressed as a %. More the discount rate lesser is the energy cost of the pump)
• Inflation Rate: Double (not mandatory, default: 0) (Inflation rate is the rate by
which prices rise expressed as a %. More the inflation rate greater is the energy cost
of the pump)
102
Figure II.7: Pump Tab of JalTantra
• Pipes without Pumps: (not mandatory, default:no constraint) (List of pipes that
cannot have Pumps)
Figure II.8: Node Results Tab of JalTantra
Results Tab: Figure II.8 displays the content of the Results tab. This tab displays
the results of the optimization. The results are broken down into details in various subtabs:
• Node Tab: Nodewise results including head and pressure values for each node
• Pipe Tab: Pipewise results including flow, diameter, headloss, headlossperkm and
cost for each pipe
103
• Cost Tab: Cost results for each diameter of commercial pipe
• ESR Tab: Cost results for each ESR to be constructed
• Pump Tab: Cost results for each Pump to be installed
Map Tab: The available options available in the Map tab are summarized below:
• Transfer Data: Transfer the node and pipe information to the nodes and pipes tab
• Close Chart: Deselect the currently selected pipe and close its associated elevation
chart
• Search Location: Search for a location on the map (type in the location and select
from the dropdown menu or press enter. Can also enter lat, long information)
• Add Node: Add a node to the map (Click on the button then click on a point on the
map. Once added you can modify the node name and id and also change location
by either entering the lat/long info or manually moving the node. You can also set
if this node is the source node or an ESR node)
• Add Pipe: Add a pipe between two nodes on the map (Click on the button then
click on two existing nodes on the map one by one)
• Right click the map: Provides options to add/edit/delete nodes, add/delete/split

pipes or close the elevation chart
• Right click a node: Provides options to delete or edit the node. (Deleting the node
removes all pipes connected to it)
• Right click a pipe: Provides options to delete/split a pipe or close the elevation
chart. (Splitting a pipe adds a node at the split point and creates two pipes instead
of the original one)
104
Appendix III
Karegaon Scheme Redesign
III.1 Background
Located at about 120 km from Mumbai on its North East side, Mokhada Taluka, is a block
in Palghar district of Maharashtra state. In spite of high rainfall in the range of 3000 mm
to 4000 mm, there are currently around 30 villages (70 habitations) in the Taluka that are
perpetually dependent on tanker supplied water during pre-summer and summer months.
Irony is that this tribal dominated area with a hilly terrain also has the distinction of
being the biggest supplier of drinking water to Mumbai city. It hosts two big reservoirs
namely, Upper Vaitarna and Middle Vaitarna, supplying over 1000 million litres of water
per day (MLD). To augment water supply to Mumbai by 455 MLD, the Middle Vaitarna
project on Vaitarna River in this Taluka was recently commissioned. The construction of
the dam on Middle Vaitarna submerged the source of the Karegaon Rural Water Supply
Scheme which supplies drinking water to four villages besides Karegaon village. When
Karegaon scheme was revamped because of submergence of its assets in the backwater
of the dam, the people in the neighbouring water-scarce villages were upset over the fact
that they were not included in the scope of redesigned scheme. They do not object to
their water being taken away as long as their need of drinking water is addressed.
III.2 CTARA Proposal for Redesign of Karegaon Scheme

The coverage area of revamped Karegaon scheme was restricted to five villages, namely,
Karegaon, Kaduchiwadi, Kochale, Bhasmyachiwadi, and Karegaon Ashramshala. In 2013,
a study was undertaken by CTARA, IIT Bombay [33] to evaluate the feasibility of aug-
mentation of scope of Karegaon scheme to include a cluster of 13 tanker fed villages in its
neighbourhood. The primary objective of the study was evaluation of techno economic
feasibility of a multi village water supply scheme (MVS) to supply drinking water to
the cluster of tanker fed villages in the neighbourhood of Karegaon scheme in Mokhada
Taluka. A step by step process following guidelines and protocols used by Maharashtra
105
Figure III.1: Tanker Fed Villages in Mokhada Taluka
Jeevan Pradhikaran (MJP) in their design process was used for this purpose. The sec-
ondary objective was to understand the process thoroughly and identify where and how
the process could be improved.
III.3 Scheme Design Process and Design Options
III.3.1 Source Selection
There were two alternative sources under consideration, Middle Vaitarna reservoir as per
current assumption of Karegaon scheme. The other alternative was to consider Upper
Vaitarna reservoir as source. The Full Supply Level of middle Vaitarna is 285 m while the
same for Upper Vaitarna is 603 meters. Hence the latter offers considerable advantage
over the former due to its high elevation in terms of savings not only in capital cost but
also in energy costs. Earlier studies indicated that the scheme based on Middle Vaitarna
as source is not feasible. This is because several villages are at higher elevations (average
elevation: 360m) than the former source (285m elevation). Hence, Upper Vaitarna was
chosen as the source.
III.3.2 Population and Demand Forecast
Population for the year 2001 and 2011 was got from census data [12]. Using this data,
projections for the year 2030 were made using the incremental and geometric methods
(assuming construction in year 2015 and a 15 year design). To get our projection we then
take the average of the two methods. This gives us a total projected population of 48407
for the year 2030.
106
Incremental method:
Projected population = Current population + decadal growth * (no. of years/10)
Geometrical method:
Projected population = Current population * (1 + decadal growth rate)(no. of years/10)
Drinking water demand was estimated from the projected population at 40 lpcd
(litres per capita per day). This gives a total demand of 1.94 million litres per day (MLD)
for the 17 villages. A further 20% loss factor was added to the demand. This gives us a
total supply requirement of 2.32 MLD. Village wise population and demand is detailed in
table III.1 below.
Table III.1: Details of the tanker fed villages in Mokhada Taluka

Population Population Demand Elevation
Village Name
(2011) (2041 est.) (litres per day) (m)
Kiniste 939 2957 1,18,280 460

Udhale 1064 2281 91,240 422
Jogalwadi 812 2245 89,800 426
Khodala 2807 7721 3,08,840 434
Sayade 1770 3006 1,20,240 420
Gomghar 1228 1536 61,440 419
Shirasgaon 526 1454 58,160 243
Dolhare 1141 1838 73,520 380
Nashera 733 4179 1,67,160 354
Adoshi 923 1060 42,400 202
Dhamanshet 1241 3431 1,37,240 384
Palsunde 1365 3774 1,50,960 393
Pathardi 661 4153 1,66,120 192
Kochale 609 1684 67,360 345
Ashramshala 750 2073 82,920 350
Karegaon 1196 3306 1,32,240 350
Kaduchiwadi 618 1709 68,360 350
Total 18,381 48,407 19,36,280
III.3.3 WTP and MBR
Water Treatment Plant is generally designed for a capacity of total daily demand. This
includes the demand calculation along with any losses. The cost estimation for the WTP
was done by extrapolating from the WTP cost of the Khardi scheme [69]. In the Khardi
107
scheme a WTP of capacity 1 MLD costs Rs 26 lakhs. For us the daily demand is 2.3
MLD. Accordingly we priced our WTP at 26 * 2.3 * 1.1 = Rs 66 lakhs. The 1.1 factor is
to account for an inflation of 10% in prices. The MBR was designed with a capacity of
one third the daily demand i.e. 0.77 MLD. The cost estimation for the MBR was done
from the MJP schedule of rates. This gave us a cost of about Rs 30 lakhs.
III.3.4 Pumping Machinery and Rising Main
Water has to be pumped at two places: from Source to WTP and from WTP to MBR.
The lowest draw level of source is 595m. The elevation of WTP and MBR is 631m and
640m respectively. The diameter of the rising mains is calculated using the flow of water
required and assuming a velocity of 1.25 m/s.
dailydemand
f low =
time
2.3M LD
⇒f low = =∼ 53.8 lps
12hours
r
f low
dia = 2 ∗
s π ∗ vel
53.8 lps
⇒dia = 2 ∗ =∼ 234mm
π ∗ 1.25 m/s
We round up this value and use a diameter of 250mm.

Raw water rising main: The distance is of 500m and diameter required is 250mm.
Due to the high flow we choose D.I. pipe for the rising main. This gives us a cost of ∼
Rs 13.3 lakhs for the rising main. Pure water rising main: The distance is of 650m and
the diameter is 250mm as before. We again use D.I. pipe which gives us a cost of ∼ Rs
17.3 lakhs.
Pumping machinery: Pump capacity required is calculated using the flow rate of water
that needs to be pumped and the head difference. For raw water rising main it is 53.8 lps
and head difference of 50m. Assuming an efficiency of 70% we get a power requirement
of ∼ 50hp. Similarly for the pure water rising main, we have a flow of 53.8 lps and head
difference of 25m which gives us a pump power requirement of 25hp. Cost for the two
pumps is calculated by comparing it with the cost of a 100hp pump in Khardi scheme
which was 22 lakhs. So our 50hp and 25hp pumps cost 11 lakhs and 5.5 lakhs respectively.
III.3.5 ESRs
Water is distributed to all the ESRs in the network by gravity. All the villages are marked
on Google Earth. ESR is generally designed for 50% of the daily demand serviced by the
ESR. The staging height is varied until an optimum point is reached. The cost of ESR goes
108
up along with increase in staging height but it is compensated by reduction in pipe size
of the secondary network due to availability of higher head and corresponding reduction
in cost. Similarly for a higher height the primary network needs to provide a higher head
and thus pipes with larger diameter are required which increases the primary network
cost. In the present study this optimization is not considered and all the cost estimations
are done based on the staging height of 10m. The choice of ESR location crucially decides
the cost of the network. This is because fixing the ESR, fixes the primary and secondary
networks. Several ESR configurations must be considered. The cost of ESRs rises sub
linearly with increasing capacity. For example a 1 lakh litre capacity ESR costs Rs 13.12
lakhs (at 2011-12 prices) and a 2 lakh litre capacity ESR costs Rs 18.87 lakhs. Therefore
to minimize ESR cost the optimum option is to have one big ESR for the entire network.
But with additional number of ESRs the piping cost goes down. So the optimum ESR
configuration can go anywhere from one to the number of villages in the network. In the
present study we place an ESR at each village. But this may not be always true since it
depends on the actual pipe network and its configuration. The ESR capacity and cost for
each village are detailed in table III.2 below.
Table III.2: Details of the Elevated Storage Reservoirs in the Mokhada Scheme
Village Population Demand Elevation ESR Cost of
Name (2041 est.) (l per day) (m) Capacity (l) ESR (Rs)
Kiniste 2957 1,18,280 460 71000 11,54,340

Udhale 2281 91,240 422 55000 10,01,700
Jogalwadi 2245 89,800 426 54000 9,92,160
Khodala 7721 3,08,840 434 186000 19,22,840
Sayade 3006 1,20,240 420 73000 11,73,420
Gomghar 1536 61,440 419 37000 7,61,080
Shirasgaon 1454 58,160 243 35000 7,31,400
Dolhare 1838 73,520 380 45000 8,79,800
Nashera 4179 1,67,160 354 101000 13,97,875
Adoshi 1060 42,400 202 26000 5,97,840
Dhamanshet 3431 1,37,240 384 83000 12,56,100
Palsunde 3774 1,50,960 393 91000 13,19,700
Pathardi 4153 1,66,120 192 100000 13,91,250
Kochale 1684 67,360 345 41000 8,20,440
Ashramshala 2073 82,920 350 50000 9,54,000
Karegaon 3306 1,32,240 350 80000 12,32,250
Kaduchiwadi 1709 68,360 350 42000 8,35,280
Total 48407 19,36,280 11,70,000 1,84,21,475
109
III.3.6 Primary Distribution Network
Figure III.2: Network Layout of the Mokhada Scheme
The pipe network is marked on Google Earth connecting the MBR to the ESRs.
The pipes are laid out on the existing road network. We can now extract the distance
details from Google Earth. Dummy nodes are marked to take care of changing elevation
along paths. This is because water not only has to reach the end point but also it has
to meet the minimum head requirement of 7m at the highest point along the path. Now
one of the most important considerations is what should be the diameter of the pipe that
needs to be laid out so that sufficient head is maintained at all points of the network.
Smaller the diameter, smaller is the cost but greater the headloss which may cause points
in the network to not receive water. To determine the pipe diameters we use a software
BRANCH [53]. Given the pipe network and the elevation and demand of the nodes, it
gives us the diameters of the pipes that need to be used to satisfy the demand while
maintaining the head requirements. The choice of pipe quality depends on the maximum
pressure that the pipe is under throughout its length. Greater the pressure, greater the
thickness of the pipe required and more the cost of the pipe. If pressure is high and one
can do with lower pressures then pressure reducing valves or break-pressure reservoirs can
be utilized. This would lower downstream pressures resulting in lower pipe costs. Pipes
in the network are HDPE pipes rated to withstand 80m of head. Where higher head is
required we use D.I. K-9 pipes which can withstand upto 400m of head (marked * in table
III.3 below). The final layout of WTP, MBR, ESRs and pipes is shown in figure III.2.
110
Table III.3: Details of the Pipe Network in the Mokhada Scheme
Peak
Sr. From To Dia Headloss HL/km Length Cost
Flow
No. Node Node (mm) (m) (m) (m) (1000 Rs)
(lps)
1* MBR Khodala 53.76 200 59.48 12.95 4595 8523.73
225 38.78 7.29 5316 9861.18
2 Khodala 3 21.39 160 21.84 6.98 3130 1993.81
3 3 2 18.90 140 12.09 10.64 1137 557.04
160 8.07 5.55 1455 926.96
4 2 Udhale 2.53 63 7.26 12.58 577 56.55
5 2 1 16.37 140 7.74 8.15 950 465.5
6 3 Jogalwadi 2.49 63 3.47 12.22 284 27.83
7 Khodala 21 1.70 63 3.77 6.02 626 61.35
8 21 Gomghar 1.70 63 14.65 6.03 2430 238.14
9* Khodala Shirasgaon 7.41 90 60.60 16.17 3747 3900.63
10 Shirasgaon Adoshi 5.79 75 66.61 24.90 2675 390.55
11 Adoshi 25 4.61 75 40.83 16.33 2500 365.00
12 25 Pathardi 4.61 75 32.67 16.33 2000 292.00
13 Khodala 4 14.68 125 25.23 11.57 1181 462.95
* 14.68 125 25.23 11.57 1000 1594.68
14 4 22 4.64 75 77.69 16.53 4700 686.20
15 22 Nashera 4.64 75 13.03 16.54 788 115.05
16 4 Dolhare 10.04 110 59.44 10.68 5568 1609.15
17 Dolhare 23 3.81 75 23.08 11.48 2010 293.46
18 23 Dhamanshet 3.81 75 16.68 11.48 1453 212.14
19 Dolhare 24 4.19 90 11.27 5.64 2000 392.00
20 24 26 4.19 90 17.80 5.63 3160 619.36
21 26 Palsunde 4.19 75 16.61 13.69 1214 177.20
90 1.39 5.64 246 48.28
22 1 Sayade 3.34 63 29.26 21.04 1391 136.32
23 1 29 13.03 140 5.93 5.34 1110 543.90
24 29 30 5.16 110 1.87 3.12 600 173.40
25 30 Kiniste 3.29 90 7.20 3.60 2000 392.00
26 30 32 1.87 63 15.11 7.20 2100 205.80
27 32 Kochale 1.87 63 1.80 7.20 250 24.50
28 29 31 7.87 90 36.16 18.08 2000 392.00
29 31 Ashramshala 2.30 63 4.22 10.55 400 39.20
30 31 Karegaon 3.67 75 21.42 10.71 2000 292.00
31 31 Kaduchiwadi 1.90 63 13.33 7.41 1800 176.40
Total 68393 36246.26
*Links where D.I. K-9 pipes are used to withstand upto 400m of pressure.
111
III.3.7 Verification of Network using EPANET
Figure III.3: EPANET model of the Mokhada Scheme Network
The network design was verified by using EPANET [68]. EPANET is a software
tool that models the flow of water in pressurized piped networks. After completing the
sizing and locations of the pipes and ESRs we construct the network in EPANET to verify
whether sufficient head is being realized at all nodes. EPANET allows analysing how the
various ESRs in the network fill up and empty during the daily life cycle. This helps
indicates if there are any “problem” nodes where sufficient head is not being met. As can
be seen in figure III.4, upstream villages get filled up first. Khodala in particular being
the first village in the network gets filled up within the first hour. Other villages gradually
fill up and empty during the demand period which is hours 9-12 and 21-24. Note that
supply occurs at hours 1-6 and 13-18.
112
Figure III.4: Water Heads at various nodes over time in the Mokhada Scheme
III.3.8 Capital Cost
The proposed multi village scheme for supplying piped water to 17 from Upper Vaitarna
has an estimated capital cost of Rs. 13.99 crores. This amounts to a per capita cost of Rs.
2890 per for a design population of 48407. The cost breakup across various components
is detailed in table III.4.
Table III.4: Details of the Capital cost of the Mokhada Scheme

Sr. Cost Base Cost Misc. Net Cost
No. Component (Rs) Factor (Rs)
1 Jack Well 25,00,000 1 25,00,000

2 WTP 66,45,313 1 66,45,313
3 Raw water rising main (Length 500m, Dia. 250mm) 13,28,405 1.479 19,64,711
4 Pure water rising main (Length 650m, Dia. 250mm) 17,26,927 1.379 23,81,432
5 MBR 30,59,408 1.151 35,21,379
6 Cost of raw water pump (50HP) 11,00,000 3.185 35,03,500
7 Cost of pure water pump (25HP) 5,50,000 2.652 14,58,600
8 Excavation 2,05,17,900 1.273 2,61,19,287
9 Piping 3,86,99,749 1.273 4,92,64,781
10 ESRs 2,02,63,623 1.142 2,31,41,057
11 Tertiary Network 1,59,06,008 1 1,59,06,008
12 M.S.E.B. 20,00,000 1 20,00,000
13 Land Acquisition 15,00,000 1 15,00,000
14 Total Cost 13,99,06,066
15 Cost per capita 2890.20
113
114
References
[1] Alperovits, Elyahu, and Uri Shamir. ”Design of optimal water distribution systems.”
Water resources research 13.6 (1977): 885-900.
[2] Assembly, G. (2015). Sustainable Development Goals. (SDGs), Transforming our

world: the, 2030.
[3] Babayan, A., Kapelan, Z., Savic, D., and Walters, G. (2005) Least-cost design of
water distribution networks under demand uncertainty. Journal of Water Resources
Planning and Management, 131(5):375–382.
[4] Bentley (2019) Water distribution and analysis design software. Accessed Au-
gust 28, 2019, https://www.bentley.com/en/products/product-line/hydraulics-and-
hydrology-software/watergems.
[5] Bhaduri, A., Bogardi, J., Siddiqi, A., Voigt, H., Vörösmarty, C., Pahl-Wostl, C., and
Kremer, H. (2016). Achieving sustainable development goals from a water perspec-
tive. Frontiers in Environmental Science, 4, 64.
[6] Bhave, P. R. (1979) Selecting pipe sizes in network optimization by LP. Journal of
the Hydraulics Division, 105(7):1019–1025.
[7] Bhave, P. R. (1981). “Node flow analysis of water distribution systems.” J. Transp.
Eng., 107(4), 457–467.
[8] Bhave, P. R. and Lam, C. F. (1983) Optimal layout for branching distribution net-
works. Journal of Transportation Engineering, 109(4):534–547.
[9] Berkelaar, M., Eikland, K., and Notebaert, P. (2006). lpsolve, version 5.5. Eindhoven
University of Technology, http://sourceforge. net/projects/lpsolve.
[10] Bouchart, F. and Goulter, I. (1991) Reliability improvements in design of wa-

ter distribution networks recognizing valve location. Water Resources Research,
27(12):3029–3040.
[11] Calhoun, C. A. (1971) Optimization of pipe systems by linear programming. In Tullis,

J. P., editor, Control of Flow in Closed Conduits, pages 175–192. Colorado State
University, Ft. Collins.
115
[12] Chandramouli, C., and Registrar General. ”Census of India 2011.” Provisional Pop-
ulation Totals. New Delhi: Government of India (2011).
[13] Chase, D. V., and Ormsbee, L. E. (1989). ”Optimal Pump Operation of Water Dis-
tribution Systems with Multiple Storage Tanks.” Proc. Conf. on Water Resources
Planning and Management, ASCE, New York, 733-736.
[14] da Conceicao Cunha, Maria, and Luisa Ribeiro. ”Tabu search algorithms for water
network optimization.” European Journal of Operational Research 157.3 (2004): 746-
758.
[15] Cunha, M. D. C. and Sousa, J. (1999) Water distribution network design optimiza-
tion: Simulated annealing approach. Journal of Water Resources Planning and Man-
agement, 125(4):215–221.
[16] Dandy, G. C., Simpson, A. R., and Murphy, L. J. (1996) An improved genetic algo-
rithm for pipe network optimization. Water Resources Research, 32(2):449–458.
[17] Dagre javascript library,(Jan, 2017), https://github.com/cpettitt/dagre/wiki
[18] De Corte, Annelies, and Kenneth Sörensen. ”HydroGen: an artificial water distribu-
tion network generator.” Water resources management 28.2 (2014): 333-350.
[19] Duan, N., Mays, L. W., and Lansey, K. E. (1990) Optimal reliability-based design of
pumping and distribution systems. Journal of Hydraulic Engineering, 116(2):249–268.
[20] Eiger, G., Shamir, U., and Ben-Tal, A. (1994) Optimal design of water distribution
networks. Water Resources Research, 30(9):2637–2646.
[21] Eusuff, Muzaffar M., and Kevin E. Lansey. ”Optimization of water distribution net-
work design using the shuffled frog leaping algorithm.” Journal of Water Resources
Planning and Management 129.3 (2003): 210-225.
[22] Forrest J, Lougee-Heimer R (2014) CBC user guide. Accessed July 15, 2019,
https://pubsonline.informs.org/doi/pdf/10.1287/educ.1053.0020.
[23] Fujiwara, O. and Dey, D. (1988) Method for optimal design of branched networks on
flat terrain. Journal of Environmental Engineering, 114(6):1464–1475.
[24] Fujiwara, Okitsugu, and Debashis Dey. ”Two adjacent pipe diameters at the optimal
solution in the water distribution network models.” Water Resources Research 23.8
(1987): 1457-1460.
116
[25] Fujiwara, O., Jenchamahakoon, B., and Edirisinghe, N. C. P. (1987) A modified
linear programming gradient method for optimal design of looped water distribution
networks. Water Resources Research, 23(6):977–982.
[26] GLPK, (GNU Linear Programming Kit), (Accessed April, 2015),

https://www.gnu.org/software/glpk/
[27] Google Maps Platform (2017) Maps JavaScript API: Overview. Accessed January 3,
2017, https://developers.google.com/maps/documentation/javascript/.
[28] Google OR Tools, (Jan, 2017), https://developers.google.com/optimization/
[29] Goulter, I. C. and Bouchart, F. (1990) Reliabilty-constrained pipe network model.

Journal of Hydraulic Engineering, 116(2):211–229.
[30] Goulter, I. C. and Coals, A. V. (1986) Quantitative approaches to reliability assess-

ment in pipe networks. Journal of Transportation Engineering, 112(3):287–301.
[31] Gupta, R., & Bhave, P. R. (1994). Reliability analysis of water-distribution systems.
Journal of Environmental Engineering, 120(2), 447-461.
[32] Halhal, D., Walters, G. A., Ouazar, D., & Savic, D. A. (1997). Water network rehabil-
itation with structured messy genetic algorithm. Journal of water resources planning
and management, 123(3), 137-146.
[33] Hooda, Nikhil, Desai, Rajaram, and Damani Om. “Design and Optimization of Piped
Water Network for Tanker Fed Villages in Mokhada Taluka” Technical Report No.
TR-CSE-2013e-55, 2013, Dept. of Computer Science and Engineering, IIT Bombay.
[34] Jacoby, S. L. S. (1968) Design of optimal hydraulic networks. Journal of the Hy-
draulics Division, 94(3):641–661.
[35] Java 7, (Sep, 2014), http://java.com/en/download/index.jsp
[36] Java ILP – Java interface to ILP solvers, (April, 2015),

http://javailp.sourceforge.net/
[37] jQuery JavaScript Library. https://jquery.com/
[38] Karmeli, D., Gadish, Y., and Meyers, S. (1968) Design of optimal water distribution
networks. Journal of Pipeline Division, 94(1):1–10, 1968.
[39] Karmarkar, Narendra. ”A new polynomial-time algorithm for linear programming.”

Proceedings of the sixteenth annual ACM symposium on Theory of Computing.
ACM, 1984.
117
[40] Lansey, Kevin E., and Larry W. Mays. ”Optimization model for water distribution
system design.” Journal of Hydraulic Engineering 115.10 (1989): 1401-1418.
[41] Lansey, K. E., Duan, N., Mays, L. W., and Tung, Y. K. (1989) Water distribu-
tion system design under uncertainties. Journal of Water Resources Planning and
Management, 115(5):630–645.
[42] Lejano, Raul P. ”Optimizing the layout and design of branched pipeline water dis-
tribution systems.” Irrigation and Drainage Systems 20.1 (2006): 125-137.
[43] Mahmoud, H. A., Savić, D., and Kapelan, Z. (2017). New pressure-driven approach
for modeling water distribution networks. Journal of Water Resources Planning and
Management, 143(8), 04017031.
[44] Maier, H. R., Simpson, A. R., Zecchin, A. C., Foong, W. K., Phang, K. Y., Seaha, H.
Y., and Tan, C. L. (2003) Ant colony optimization for design of water distribution
systems. Journal of Water Resources Planning and Management, 129(3):200–209.
[45] Maier, H. R., Kapelan, Z., Kasprzyk, J., Kollat, J., Matott, L. S., Cunha, M. C.,
Dandy, G. C., Gibbs, M. S., Keedwell, E., Marchi, A., Ostfeld, A., Savic, D., Solo-
matine, D. P., Vrugt, J. A., Zecchin, A. C., Minsker, B. S., Barbour, E. J., Kuczera,
G., Pasha, F., Castelletti, A., Giuliani, M., and Reed, P. M. (2014). ”Evolutionary
Algorithms and Other Metaheuristics in Water Resources: Current Status, Research
Challenges and Future Directions.” Environmental Modelling and Software, 62, 271-
299.
[46] Mala Jetmarova, Helena, Nargiz Sultanova, and Dragan Savic. ”Lost in optimisation
of water distribution systems? A literature review of system operation.” Environ-
mental Modelling and Software 93 (2017): 209-254.
[47] Mala-Jetmarova, Helena, Nargiz Sultanova, and Dragan Savic. ”Lost in optimisation
of water distribution systems? A literature review of system design.” Water 10.3
(2018): 307.
[48] Mandry, J. E. (1967) Design of pipe distribution systems for sprinkler projects. Jour-
nal of Environmental Engineering, 93(3):243–257.
[49] Maharashtra Jeevan Pradhikaran (MJP), Schedule of Rates for Konkan Region: Civil
Works for Year 2018-19, (2018).
[50] Montesinos, P., Garcia-Guzman, A., and Ayuso, J. L. (1999) Water distribution
network optimization using a modified genetic algorithm. Water Resources Research,
35(11):3467–3473.
118
[51] Nicklow, J., Reed, P., Savic, D., Dessalegne, T., Harrell, L., Chan-Hilton, A.,
Karamouz, M., Minsker, B., Ostfeld, A., Singh, A., and Zechman, E. (2010). ”State of
the Art for Genetic Algorithms and Beyond in Water Resources Planning and Man-
agement.” Journal of Water Resources Planning and Management, ASCE, 136(4),
412-432.
[52] Papadimitriou, Christos H. ”On the complexity of integer programming.” Journal of

the ACM (JACM) 28.4 (1981): 765-768.
[53] Prasad M. Modak, Juzer Dhoonia, “A Computer Program in Quick BASIC for the
Least Cost Design of Branched Water Distribution Networks.” UNDP/ World Bank,
Asia Water Supply and Sanitation Sector Development Project, RAS/86/160, De-
cember 1991.
[54] Robinson, R. B. and Austin, T. A. (1976) Cost optimization of rural water systems.
Journal of the Hydraulics Division, 102(8):1119–1134.
[55] Samani, Hossein MV, and Alireza Mottaghi. ”Optimization of water distribution
networks using integer linear programming.” Journal of Hydraulic Engineering 132.5
(2006): 501-509.
[56] Sankar, G. S., Kumar, S. M., Narasimhan, S., Narasimhan, S., and Bhallamudi, S.
M. (2015). Optimal control of water distribution networks with storage facilities.
Journal of Process Control, 32, 127-137.
[57] Savić, D., and Ferrari, G. (2014). Design and performance of district metering areas
in water distribution systems. Procedia Engineering, 89, 1136-1143.
[58] Savic, Dragan A., and Godfrey A. Walters. ”Genetic algorithms for least-cost design
of water distribution networks.” Journal of Water Resources Planning and Manage-
ment 123.2 (1997): 67-77.
[59] Sayyed, M. A., Gupta, R., and Tanyimboh, T. T. (2014). “Modelling pressure defi-
cient water distribution networks in EPANET.” Procedia Eng., 89, 626–631.
[60] Schaake, J.C.; Lai, D. Linear Programming and Dynamic Programming Application
to Water Distribution Network Design; Report No. 116; Hydrodynamics Laboratory,
Department of Civil Engineering, Massachusetts Institute of Technology: Cambridge,
MA, USA, 1969.
[61] Schwarz, J., Meidad, N., and Shamir, U. (1985). ”Water Quality Management in
Regional Systems.” Scientific Basis for Water Resources Management, IAHS Publ.
no. 153, Proceedings of the Jerusalem Symposium, September 1985.
119
[62] Shamir, U. (1974) Optimal design and operation of water distribution systems. Water
Resources Research, 10(1):27–36, 1974.
[63] Simpson, A. R., Dandy, G. C., and Murphy, L. J. (1994) Genetic algorithms compared
to other techniques for pipe optimization. Journal of Water Resources Planning and
Management, 120(4):423–443.
[64] Su, Y., Mays, L. W., Duan, N., and Lansey, K. E. (1987) Reliability-based opti-
mization model for water distribution systems. Journal of Hydraulic Engineering,
114(12):1539–1556.
[65] Swamee, P. K., Kumar, V., and Khanna, P. (1973) Optimization of dead end water
distribution system. Journal of Environmental Engineering Division, 99(2):123–134.
[66] Thornton, Julian, R. Sturm, and G. Kunkel. Water loss control manual. New York:
McGraw-Hill, 2002.
[67] Tuttle, G. W. ”The economic velocity of transmission of water through pipes.” En-
gineering Record 32.15 (1895): 258-258.
[68] United States Environmental Protection Agency (2017) EPANET: Application for
modeling drinking water distribution systems. Accessed June 1, 2019,
http://www.epa.gov/nrmrl/wswrd/dw/epanet.html.
[69] V. Choudhary, O. Damani, R. Desai, A. Joshi, M. Kanwat, M. Kaushal, S. Kharole

,Kharole, Y. Pawde, P. Rathore, and M. Sohoni. “Redesigning Khardi Rural Piped
Water Network Scheme for Sustainability” Technical Report No. TR-CSE-2013-56,
2013, Dept. of Computer Science and Engineering, IIT Bombay.
[70] Van Zyl, J. E., Savic, D. A., and Walters, G. A. (2004). ”Operational Optimization
of Water Distribution Systems Using a Hybrid Genetic Algorithm.” Journal of Water
Resources Planning and Management, ASCE, 130(2), 160-170.
[71] Vyas, Janki H., Narendra J. Shrimali, and Mukesh A. Modi. “Optimization of
Dhrafad Regional Water Supply Scheme using Branch 3.0.”, IJIRSET 2014
[72] w2ui JavaScript Library. http://w2ui.com/web/
[73] Watanatada, T. (1973) Least-cost design of water distribution systems. Journal of

the Hydraulics Division, 99(9):1497–1513.
[74] Williams, Gardner Stewart, and Allen Hazen. ”Hydraulic tables.” (1933).
120
[75] Wu, Z. Y. and Simpson, A. R. (2001) Competent genetic-evolutionary optimization of
water distribution systems. Journal of Computing in Civil Engineering, 15(2):89–101.
[76] Xu, C. and Goulter, I. C. (1999) Reliabilty-based optimal design of water distribution
networks. Journal of Water Resources Planning and Management, 125(6):352–362.
[77] Yates, D. F., A. B. Templeman, and T. B. Boffey. ”The computational complexity

of the problem of determining least capital cost designs for water supply networks.”
Engineering Optimization 7.2 (1984): 143-155.
[78] Young, B. (1994) Design of branched-water-supply network on uneven terrain. Jour-

nal of Environmental Engineering, 120(4):975–979.
[79] Yugandhara Lad, J S Main, and S D Chawathe. “Optimization of Hydraulic Design

of Water Supply Tree Network Based on Present Worth Analysis.” Journal of Indian
Water Works Association, 2012.
121
122
List Of Publications
Published
• Hooda, Nikhil, and Om Damani. ”A system for optimal design of pressure con-
strained branched piped water networks.”, 18th Conference on Water Distribution
System Analysis, WDSA (2016).
• Hooda, Nikhil, and Om Damani. ”Inclusion of tank configurations as a variable

in the cost optimization of branched piped-water networks.” Drinking Water Engi-
neering and Science 10.1 (2017): 39-44.
Accepted
• Hooda, Nikhil, and Om Damani, “JalTantra: A System for Design and Optimization
of Rural Piped Water Networks”, INFORMS Journal on Applied Analytics
• Hooda, Nikhil, Ashutosh Mahajan, and Om Damani, ”A Series of ILP Models for
the Optimization of Water Distribution Networks”, SADHANA
123
124
Acknowledgements
I would like to thank my supervisor, Prof. Om P. Damani for his constant guid-
ance, encouragement and patience throughout the duration of my study. Conversations
with him were always enlightening, be they on the research topic or about the world
in general. I have relied on his advice from before the research work started and I am
sure I will continue to do so in the future as well. I thank the members of my research
progress committee, Prof. Milind Sohoni, Prof. Ashutosh Mahajan and Prof. Sundar
Vishwanathan. Their diverse expertise provided invaluable feedback which helped direct
and refine the research work.
Special thanks are in order for Prof. Puru Kulkarni, Raj Desai, Abhishek Sinha,
Ashish Karale and Vaishali Bharambe from the Centre for Technology Alternatives for
Rural Areas (CTARA). The work done by the team at CTARA was the genesis for this
thesis. The students of the Technology and Development Supervised Learning (TDSL)
course did the field survey and analysis of existing and planned water schemes, providing
us with an invaluable resource for understanding the design process. In particular I thank
Raj sir for being the interface between the practical and the theoretical. It was through
him that we were able to interact with numerous government engineers and understand
the challenges they face. I thank the engineers from Maharashtra Jeevan Pradhikaran,
Santosh Gawankar, Mahesh Patil, Brajesh Sengar and Pradeep Gokhale, who listened
to us patiently, answered our questions and then provided invaluable feedback on the
JalTantra system.
I thank Dipak Chaudhri for his guidance on all things research at IITB. I thank
the office staff at Computer Science Department at IIT Bombay for their assistance. In
particular, for their patience and prompt help, I thank Vijay Ambre and Sunanda Ghadge.
I thank the Ministry of Human Resource Development (MHRD), Government of
India for the PhD assistantship and Tata Consultancy Services (TCS) for supporting me
through a research fellowship.
I thank Vijay Arya and Pratyush Kumar from IBM, Bangalore for hosting me
during my summer intern.
Most of all, I thank my parents, Surender and Rachna Hooda and my sister Garima
Hooda. My research work would not be possible without their constant unconditional love
and support. I hope I can live upto their expectations.
125
126

Design and Optimization of Branched Piped Water Networks

Uploaded by

Copyright:

Available Formats

Design and Optimization of Branched Piped Water Networks

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Design and Optimization of Branched Piped Water Networks

Uploaded by

Copyright:

Available Formats

Design and Optimization of

Branched Piped Water Networks

Submitted in partial fulfillment of the requirements of the degree of

Under the Supervision of

Department of Computer Science and Engineering

Government bodies responsible for drinking water distribution in developing countries

Keywords: Water Distribution; Optimization; Integer Linear Program; Pipe Diameter

List of Figures xiii

List of Tables xiv

List of Abbreviations xvi

3 Components of a Rural Piped Water Scheme 17

4 Pipe Diameter Optimization 21

5 ESR Sizing and Allocation 31

8 Edge Based Model 75

9 JalTantra System Description 81

10 Conclusion and Future Work 87

I Complete ILP Model 89

II JalTantra Usage Details 97

III Karegaon Scheme Redesign 105

List Of Publications 123

1.1 Vicious Cycle Leading to Scheme Failure. . . . . . . . . . . . . . . . . . . . 2

2.1 Comparison of performance of various approaches on the two loop network 13

CBC COIN-OR Branch and Cut

• The solutions it provides must be optimal, fast and consistent.

• Existing software, used by government agencies in developing countries, look at

• Multiple refinements are done to the model by exploring alternative formulations

1.3 Structure of the Thesis

2.1 Branched Network Design

2.1.1 Linear Programming Techniques

2.1.2 Non Linear Programming Techniques

2.2 Looped Network Design

2.2.1 Deterministic Techniques

2.2.2 Metaheuristic Techniques

Length Dia Length Dia Length Dia Length Dia

1 256 20 1000 18 1000 18 1000 18

2.3.1 Reliability Considerations

2.3.2 Network Generation

2.3.3 Network Operation

Components of a Rural Piped Water Scheme

Figure 3.1: Components of a typical Rural Piped Water Scheme.

3.2 Water Treatment Plant (WTP)

3.3 Mass Balancing Reservoir (MBR)

3.4 Elevated Storage Reservoirs (ESRs)

• Typically the demand at a location would be distributed across many households.

Pipe Diameter Optimization

4.1 OnePipe Model

4.1.1 The Objective Function

N L: The number of links in the network

Ci : Cost/length of link i, a function of the pipe diameter Di

N P : Number of commercially available pipe diameters

xij : 1 if link i uses pipe diameter j, else 0

4.1.2 Pipe Constraint

4.1.3 Node Constraint

At each node a minimum amount of pressure needs to be maintained. The pressure at

Pn : The minimum pressure that must be maintained at node n

HR : The head supplied by reference node

En : The elevation of node n

N N : The number of nodes in the network

Rj : Pipe roughness of commercial pipe j