HOME     |     SERVICES     |     TEAM MEMBERS     |     FREE DOWNLOADS     |     CONTACT US

Water Resources Networks

Water resources networks are among the most difficult to solve. Since its inception in 1988, Optimal Solutions Ltd. has been involved in the development, maintenance and applications of the Water Resources Management Model (WRMM) of Alberta Environment, a Provincial Government water management agency in Canada (insert the link).  The WRMM uses Network Flow Algorithm (NFA) to derive solution for a specified set of operational priorities and physical constraints.  The company has recently developed technical specifications and a new version of this model that uses Mixed Integer Programming and a commercial LP solver instead of the NFA based on the Out-of-Kilter solution procedure.  It has been determined that network NFA could not guarantee the best solution using an iterative approach that had to be employed in water resources networks.  Iterations were due to both linear and non-linear relationship between flows on individual flow links, and the fact that an NFA allows only the simple form of fixed upper and lower bound constraints in flow links (arcs).  A typical problem related to optimization of network flows is finding the minimum cost flow in a network. A sample network in Figure 1 has 11 routes (arcs) along which a commodity can be shipped and six junctions (nodes). Associate with each arc a tail node (i) and head node (j) such that an arc can be defined by an ordered pair (i,j). For each arc (i,j) assign the upper flow capacity Uij, the lower minimum limit on flow Lij, and a cost of shipping Cij of a unit of commodity along an arc (i,j). The problem of finding a minimum cost flow in a network is then defined as a problem of finding a set of arc flows Xij such that the sum of the product of all arc costs and flows is minimized subject to the flow limitations imposed by the arc flow bounds Uij and Lij, as well as the mass balance at each node. This is mathematically expressed as:

In the above expressions N is the total number of nodes and A is the set of all arcs in the network. In the example in Figure 1 N is 6 while the maximum number of arcs A is 11. The first constraint represents the mass balance for each node while the second represents the flow limitations imposed by the arc bounds.

If parameters Uij, Lij and Cij are fixed constants, there are no mutual dependencies of flows Xij other than the nodal mass balance, the problem is termed a network flow program. A number of solution techniques are available for linear minimum cost flow problem, such as the Out-of-Kilter algorithm and its variants, RELAX 4 or the network simplex algorithm. Optimal Solutions Ltd. has developed a version of the SUPERK algorithm based on modifying some of the ideas of the original version of the SUPERK algorithm released by Barr, Glover and Klingman (1974).

Reference: Barr, R.S., F. Glover & D. Klingman 1974. An improved version of the out-of-kilter method and a comparative study of computer codes. Mathematical Programming 7, North Holland Publishing, Amsterdam, p. 60-86.

Figure 2 shows a small example water resources network that corresponds to the oriented arc flow network shown in Figure 1. They may include non-linear relationship between flows on individual flow links (arcs) both in terms of the flow bounds and cost functions. Consider the example network in Figure 2. There are three water users in the system: hydro power plant, irrigation district and the most downstream channel designated as River Reach 3 (RR3) which has its own riparian flow requirement governed by concerns associated with navigation or environmental control. The goal is to find the best water management policy (i.e. reservoir releases and diversion at the weir) for a short time horizon of a few days or a week, assuming known inflow forecasts, power requirements, irrigation demand and downstream riparian requirement. The solution can be sought for a single time interval or for many time intervals simultaneously. More information on the limitations caused by handling non-linear flow constraints using iteration is pending publication.