HLPL / VerTeX Modelling Language Documentation

← lessons

Max flow — alternative formulation

Measure flow at the sink instead.

Chapter: XI — Max flow · lesson id flow-sink-balance · practice lesson

---

An equivalent way to state max flow: maximise what arrives at the sink. By conservation, the two formulations always agree, but writing the objective at the sink makes the model robust when you forget the source side.

Change the objective to max x_{24} + x_{34} (the two edges into t). The optimum is still 12.

Bonus: in a richer formulation you'd add a variable F for total flow and constraints outflow_s − inflow_s = F, inflow_t − outflow_t = F, then max F. That's the canonical form.

Starter code

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}
# TODO: change the objective to measure flow INTO t (x_24 + x_34)
max x_{12} + x_{13}
end

import elytica
def main():
  elytica.init_model("flow")
  elytica.run_model("flow")
  print("obj =", elytica.get_best_primal_bound("flow"))
  return 0

Hint

Change one line. The objective.

What counts as correct

• no-error — Model solves
• numeric-match — Same max flow measured at the sink
• 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_{24} + x_{34}
end

import elytica
def main():
  elytica.init_model("flow")
  elytica.run_model("flow")
  print("obj =", elytica.get_best_primal_bound("flow"))
  return 0

Mastery variant

Same fresh capacities as the conservation variant. Confirm the sink sees the same total.

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}
# TODO: change the objective to measure flow INTO t (x_24 + x_34)
max x_{12} + x_{13}
end

import elytica
def main():
  elytica.init_model("flow_v")
  elytica.run_model("flow_v")
  print("obj =", elytica.get_best_primal_bound("flow_v"))
  return 0

Read this through MCP: read with path: "lessons/flow-sink-balance", or resource hlpl://lessons/flow-sink-balance.