A water distribution system14 is a network with (positive = forward or negative = reverse)

flows xi,j, in pipes between nodes i, j = 0,

c, m representing storage tanks and pipe intersections.

Pressures at the nodes i can be measured in hydraulic

“head,” which is the height to which water will rise in an openended vertical pipe installed at the node, relative to the “ground node” 0. Heads have assigned values si for storage tank nodes i, and net outflows ri are established for all nodes 1a m

i = 0 ri = 02. The ground node 0 is connected to each storage node i by an arc (0, i), and to no others. To determine how the system will perform at steady state, engineers need to find flows fi,j and heads hi that (i) maintain net flow balance at every node, (ii) achieve assigned heads si at storage nodes, and (iii) satisfy nonlinear head-toflow equations hj - hi = fi,j1fi,j2 nonground 1i, j2 where functions fi,j1xi,j2 are known relations between head difference and the flow on particular arcs 1i, j2 that reflect length, size, pumping, grade, and other characteristics.

(a) Formulate a related NLP over unrestricted flows xi,j having only flow balance constraints at all nodes and a minimizing objective function summing terms fi,j1xi,j2 e sjx0,j arcs 10, j2 1

xi, j 0 fi,j1z2dz other 1i, j2

(b) Explain why your NLP of part

(a) is a separable program. (With mild assumptions on the fi,j it can also be shown to be convex.)

(c) State Karush–Kuhn–Tucker conditions for the primal model of part

(a) and explain why they must be satisfied by a locally optimal x*.

(d) Interpret conditions of part

(c) to show that a solution to steady-state equation system (i)–(iii) above can be obtained from locally optimal flows x* in part (a)

and corresponding KKT multipliers v*.