Operators of underground water supply networks are challenged with pipe replacement decisions, because pipes are subject to increased failure rates as they age and financial resources are often limited. We study the optimal replacement time and optimal number of pipe replacements such that the expected failure cost and replacement cost are minimized, while satisfying a budget constraint and incorporating uncoordinated and coordinated replacement. Results show that coordinated replacement is economically preferred to uncoordinated replacement. It depends on the size of the budget whether the increase in the number of pipe replacements is sufficient to reduce the total expected failure cost.