HLPL / VerTeX Modelling Language Documentation

← lessons

Max flow — add conservation

Inflow = outflow at internal nodes.

Chapter: XI — Max flow · lesson id flow-conservation · practice lesson

---

A valid flow conserves at every internal node — whatever enters must leave.

node a: x_{12} = x_{23} + x_{24} node b: x_{13} + x_{23} = x_{34}

Add these two constraints and the max drops from 14 to 12. The min cut is the pair of edges into t — a→t (7) and b→t (5) — totalling 12.

Predict before running

Add conservation at the two internal nodes. What's the true max flow s→t?

• 14. Same as without conservation
• 12. Bottlenecked by the edges into t
• 11. Bottlenecked by some other cut

Starter code

model flow
# Edges (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
# TODO: conservation at node a (12 = 23 + 24) and node b (13 + 23 = 34)
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

Hint

Two constraints — one per internal node. The solver figures out the right split.

What counts as correct

• no-error — Model solves
• numeric-match — Real max flow is 12 (bottlenecked by b→t cap 5)
• code-contains — Reads the objective from the solver (no hardcoding)

Solution

model flow
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
constr x_{12} = x_{23} + x_{24}
constr x_{13} + x_{23} = x_{34}
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

Mastery variant

Same network, fresh capacities. Where's the min-cut this time?

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
constr x_{12} = x_{23} + x_{24}
constr x_{13} + x_{23} = x_{34}
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-conservation", or resource hlpl://lessons/flow-conservation.