Continuous flow on each edge.
Chapter: XI — Max flow · lesson id flow-vars-caps · practice lesson
Same kind of network, different question: how much total flow can we push from a source s to a sink t given per-edge capacities?
Network: s, a, b, t. Edges with capacities — s→a (8), s→b (6), a→b (3), a→t (7), b→t (5).
We label nodes 1=s, 2=a, 3=b, 4=t so the edge IDs read as their endpoints: edge 12 is s→a, 23 is a→b, and so on. Variables x_e are continuous (any non-negative real), each capped at its edge's capacity. The objective is the flow out of s, namely x_{12} + x_{13}.
Run it. Without conservation, the solver naively saturates the source edges — total 14. But this isn't a valid flow!
Capacities {8, 6, 3, 7, 5}, maximise total at source. No conservation yet. What does the solver report?
model flow
# Edges labelled by node pair (s=1, a=2, b=3, t=4):
# 12 = s→a 13 = s→b 23 = a→b 24 = a→t 34 = b→t
set E = {12, 13, 23, 24, 34}
const capacity = {8, 6, 3, 7, 5}, forall e in E
var 0 <= x, forall e in E
constr x_{e} <= capacity_{e}, forall e in E
max x_{12} + x_{13}
end
import elytica
def main():
elytica.init_model("flow")
elytica.run_model("flow")
for i in [12,13,23,24,34]:
print("x"+str(i), "=", elytica.get_variable_value("flow", "x"+str(i)))
print("obj =", elytica.get_best_primal_bound("flow"))
return 0
Without conservation, the solver maxes x_{12}=8 and x_{13}=6, total 14. Real max flow is lower.
no-error — Model solvesnumeric-match — Without conservation, naive max is 14 (sum of source caps)code-contains — Reads the objective from the solver (no hardcoding)Same network shape, fresh capacities. Source-saturation gives the naive answer.
model flow_v
set E = {12, 13, 23, 24, 34}
const capacity = {9, 5, 4, 6, 7}, forall e in E
var 0 <= x, forall e in E
constr x_{e} <= capacity_{e}, forall e in E
max x_{12} + x_{13}
end
import elytica
def main():
elytica.init_model("flow_v")
elytica.run_model("flow_v")
for i in [12,13,23,24,34]:
print("x"+str(i), "=", elytica.get_variable_value("flow_v", "x"+str(i)))
print("obj =", elytica.get_best_primal_bound("flow_v"))
return 0
Read this through MCP: read with path: "lessons/flow-vars-caps", or resource hlpl://lessons/flow-vars-caps.