Upstream vs. Downstream
Introduction
Picture a river that flows through six villages. The three villages at the top (upstream) get first access to the water. The three at the bottom (downstream) get whatever is left, plus a tributary that joins the river midway. Every liter pulled out upstream is a liter that downstream cannot use, yet farming and drinking water are both essential to every village.
This article formulates the problem as an optimization model, solves it exactly with linear programming, and compares the result with an uncoordinated “first come, first served” policy. We then use 3D and 2D visualizations to show how the optimal allocation moves as the upstream intake limit and the river inflow change.
Problem Setting
- Villages are indexed $i = 1,\dots,6$ from upstream to downstream. Villages $1$–$3$ are upstream, and villages $4$–$6$ are downstream.
- The river inflow at the top is $Q_0$. A tributary with flow $Q_T$ joins just after village 3.
- Village $i$ withdraws $a_i$ for agriculture and $w_i$ for domestic use, in thousand m³/day.
- A fraction $c$ of every withdrawal is consumed. The remaining $1-c$ returns to the river.
- At the river mouth, an environmental minimum flow $Q_{\mathrm{env}}$ must remain.
- The goal is to maximize the total population supported across all villages.
Mathematical Formulation
Let $P_i$ be the population (in thousands) that village $i$ can sustain. Food production saturates because arable land is limited:
$$
P_i^{\mathrm{food}}(a_i) = P_i^{\max}\left(1 - e^{-a_i/s_i}\right)
$$
Here $P_i^{\max}$ is the maximum population the land of village $i$ can feed, and $s_i$ is the water scale of its irrigation. Domestic water supports
$$
P_i^{\mathrm{dom}}(w_i) = \frac{w_i}{d}
$$
where $d$ is the per-capita domestic demand. The population is limited by the scarcer of the two:
The flow arriving at village $i$ is
$$
Q_i = Q_0 + \mathbb{1}[i \ge 4],Q_T - c\sum_{j<i}\left(a_j + w_j\right)
$$
The complete optimization problem is
$$
\begin{aligned}
\max_{a,,w,,P}\quad & \sum_{i=1}^{6} P_i \
\text{s.t.}\quad & P_i \le P_i^{\max}\left(1 - e^{-a_i/s_i}\right), \
& d,P_i \le w_i, \
& a_i + w_i \le Q_i, \
& Q_0 + Q_T - c\sum_{j=1}^{6}\left(a_j + w_j\right) \ge Q_{\mathrm{env}}, \
& a_i,\ w_i,\ P_i \ge 0
\end{aligned}
$$
The function $P_i^{\mathrm{food}}$ is concave, so the first constraint defines a convex set. Every other constraint is linear. We can therefore replace the concave curve by its tangent lines at $K$ points $\alpha_k$:
$$
P_i \le P_i^{\mathrm{food}}(\alpha_k) + \frac{dP_i^{\mathrm{food}}}{da}\bigg|_{\alpha_k}\left(a_i - \alpha_k\right), \qquad k = 1,\dots,K
$$
with
$$
\frac{dP_i^{\mathrm{food}}}{da} = \frac{P_i^{\max}}{s_i},e^{-a/s_i}
$$
The minimum of these tangents approximates the concave curve from above, and the error shrinks as $K$ grows. The problem becomes a pure linear program that HiGHS solves in milliseconds, so the 3D parameter sweep later in the article stays fast.
Example Parameters
| Village | Zone | $P_i^{\max}$ (thousand people) | $s_i$ (thousand m³/day) |
|---|---|---|---|
| U1 | Upstream | 6 | 25 |
| U2 | Upstream | 8 | 30 |
| U3 | Upstream | 5 | 20 |
| D1 | Downstream | 9 | 28 |
| D2 | Downstream | 7 | 35 |
| D3 | Downstream | 10 | 40 |
The remaining parameters are:
- Domestic demand: $d = 0.15$ thousand m³/day per thousand people (150 L per person per day)
- Consumptive fraction: $c = 0.6$
- River inflow: $Q_0 = 100$ thousand m³/day
- Tributary flow: $Q_T = 30$ thousand m³/day
- Environmental minimum flow: $Q_{\mathrm{env}} = 40$ thousand m³/day
As a baseline we use an uncoordinated policy. Each village, starting from the top, takes enough water to support 92% of its maximum population (domestic water first). It is limited only by the water physically arriving and by the total consumable budget $Q_0 + Q_T - Q_{\mathrm{env}}$.
Source Code
1 | import numpy as np |
Code Walkthrough
Parameters and helper functions
The first block defines the village names, the number of upstream villages (N_UP = 3), and the physical parameters. food_pop evaluates the saturating food curve $P_i^{\max}(1 - e^{-a_i/s_i})$ for all villages at once with NumPy broadcasting. population takes the elementwise minimum of the food-limited and water-limited populations, which is exactly $P_i = \min{P_i^{\mathrm{food}}, w_i/d}$.
Building the linear program
The decision vector is laid out as $[a_1..a_6,\ w_1..w_6,\ P_1..P_6]$, which gives 18 variables.
- Tangent constraints. For each village,
K = 80tangent points are placed from $0$ to $6 s_i$. Each tangent becomes one row $P_i - m_k a_i \le b_k$, where $m_k$ is the slope and $b_k = f(\alpha_k) - m_k \alpha_k$ is the intercept. Together these 480 rows approximate the concave food curve from above. - Domestic constraints. The rows $d P_i - w_i \le 0$ encode $P_i \le w_i/d$.
- Flow constraints. Row $i$ encodes $a_i + w_i + c\sum_{j<i}(a_j + w_j) \le Q_i^{\mathrm{in}}$. This is the arrival-flow condition: a village cannot withdraw more than what reaches it after all upstream consumption.
- Environmental constraint. A single row enforces $c\sum_j (a_j + w_j) \le Q_0 + Q_T - Q_{\mathrm{env}}$.
- Upstream intake cap. A final row limits total upstream withdrawal to
cap. It is set to a huge value (BIG) in the base case and varied during the sweep.
All of these matrices are built once outside the solver function. Only the right-hand side changes between solves, so the 693 linear programs in the parameter sweep run quickly. linprog(..., method="highs") returns the global optimum, and the minus signs in COST turn maximization into minimization. The function returns None if the solver fails, and the main code raises a clear error in that case.
Uncoordinated baseline
greedy_allocation simulates the “first come, first served” policy. Walking downstream, each village wants enough water for 92% of its maximum population (domestic water first, then irrigation). It receives the smaller of its want, the water that physically arrives, and the remaining consumable budget. Because upstream villages are served first, they can exhaust the whole budget before the water reaches the lower valley.
River profile
river_flow computes the flow after each village as $Q_0$, plus the tributary for downstream villages, minus the cumulative consumption $c\sum(a_j + w_j)$. This is the quantity compared against the environmental minimum.
Parameter sweep
The double loop solves the LP for 21 river inflows (60 to 160) and 33 upstream intake caps (0 to 160). The results are stored in three matrices holding the total, upstream, and downstream populations. These matrices feed the 3D surface, the contour map, and the stacked trade-off plot.
Visualization
All six panels are drawn in one figure with a dark theme.
- A 3D surface of the optimal total population versus intake cap and river inflow.
- A top-down contour view of the same surface, with the base-case optimum marked by a star.
- A stacked area chart of upstream and downstream population versus the intake cap at $Q_0 = 100$.
- Grouped bars of the population of each village under both policies.
- The river flow profile along the valley, with the environmental minimum and the tributary junction marked.
- A 3D bar chart comparing agricultural withdrawals in each village under both policies.
Execution Results
Result Image
Console Output
=== Allocation (thousand m3/day) and population (thousand people) ===
Village Zone Agri_opt Dom_opt Pop_opt Agri_greedy Dom_greedy Pop_greedy
U1 Upstream 19.92 0.49 3.30 63.14 0.83 5.52
U2 Upstream 26.19 0.70 4.66 60.51 1.10 6.94
U3 Upstream 15.94 0.41 2.75 23.72 0.69 3.47
D1 Downstream 30.82 0.90 6.01 0.00 0.00 0.00
D2 Downstream 21.43 0.48 3.21 0.00 0.00 0.00
D3 Downstream 31.88 0.82 5.49 0.00 0.00 0.00
Total population (optimal) : 25.41
Total population (uncoordinated) : 15.93
Improvement : 59.5 %
Upstream population (optimal) : 10.70
Downstream population (optimal) : 14.71
Upstream population (uncoord.) : 15.93
Downstream population (uncoord.) : 0.00
River mouth flow (optimal) : 40.00
River mouth flow (uncoordinated) : 40.00
Interpreting the Results
The 3D surface and contour map
The surface shows the maximum achievable total population for every combination of upstream intake cap and river inflow. Along the river-inflow axis, the surface rises as more water enters the system. Along the intake-cap axis, it rises and then flattens into a plateau. Beyond the plateau, relaxing the cap further adds nothing, because the optimizer would not use that extra upstream water anyway. In the contour view, the plateau appears as vertical contour lines. The star marks the base-case optimum at the point where the plateau begins.
The upstream versus downstream trade-off
The stacked area chart makes the conflict visible. Raising the upstream intake cap increases upstream population, but the downstream layer shrinks because less water arrives. The total is largest when the two effects are balanced. Since only 60% of each withdrawal is consumed, the return flow softens the conflict, and the optimizer takes advantage of it by directing water to the villages with the best population gain per unit of water.
Village populations and agricultural water
Under the uncoordinated policy, the upstream villages fill their demand first. The consumable budget is exhausted by the time the water reaches the lower valley, so the downstream villages receive close to nothing. The optimal plan does the opposite of “fill the top first”. Because the food curve saturates, the last units of water are worth little to a village that is already well supplied. The optimizer therefore holds back upstream intake once the marginal gain falls and sends that water downstream, where it supports far more people. The 3D bar chart shows this clearly: the pattern of agricultural withdrawals under the optimal plan is spread across the whole valley, while the uncoordinated plan is heavily concentrated at the top.
The river flow profile
Both policies respect the environmental minimum at the river mouth, but they use the water very differently. The uncoordinated policy drains the river to the environmental limit within the upstream section. The optimal policy keeps more water flowing into the lower valley, so the flow declines gradually along the whole river before reaching the same floor at the mouth.
Conclusion
We modeled a river shared by upstream and downstream villages and recast the nonlinear food-production curves as a linear program using tangent-line approximation. The result is an exact and extremely fast solver that finds the globally optimal split between agricultural and domestic water. Compared with a first-come-first-served policy, the optimal allocation supports substantially more people, because it recognizes that water is more valuable where it is scarce.
The same framework extends naturally to more villages, seasonal flow variation, canal capacity limits, or economic terms such as crop revenue. Any of these can be added as extra linear constraints or objective terms, and the solver remains fast.
