HLPL / VerTeX Modelling Language Documentation

← lessons

Shortest path — flow conservation

Force a path from source to sink.

Chapter: X — Shortest path · lesson id sp-conservation · practice lesson

---

A path is defined by flow conservation: at the source one unit flows out; at the sink one unit flows in; at every internal node, inflow equals outflow.

Translate to linear constraints:

node 1 (source): out − in = 1 → x₁₂ + x₁₃ = 1 node 2: out − in = 0 → x₂₄ − x₁₂ − x₃₂ = 0 node 3: out − in = 0 → x₃₂ + x₃₄ − x₁₃ = 0 node 4 (sink): out − in = −1 → x₂₄ + x₃₄ = 1

Run it. The solver finds 1 → 3 → 2 → 4 with cost 2 + 1 + 3 = 6.

Predict before running

Edges 1→2 (4), 1→3 (2), 3→2 (1), 2→4 (3), 3→4 (5), routing one unit from 1 to 4. What's the shortest path?

• 1 → 3 → 4 (cost 7)
• 1 → 3 → 2 → 4 (cost 6)
• 1 → 2 → 4 (cost 7)

Starter code

model sp
set E = {12, 13, 32, 24, 34}
const d = {4, 2, 1, 3, 5}, forall e in E
bin x, forall e in E
# TODO: four flow-conservation constraints, one per node
min sum_{e in E}{d_{e} * x_{e}}
end

import elytica
def main():
  elytica.init_model("sp")
  elytica.run_model("sp")
  for i in [12,13,32,24,34]:
    print("x"+str(i), "=", elytica.get_variable_value("sp", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("sp"))
  return 0

Hint

Add the four conservation constraints. Each one says "outgoing − incoming = balance".

What counts as correct

• no-error — Model solves
• numeric-match — Shortest 1→4 path costs 6 (1 → 3 → 2 → 4)
• code-contains — Reads the objective from the solver (no hardcoding)

Solution

model sp
set E = {12, 13, 32, 24, 34}
const d = {4, 2, 1, 3, 5}, forall e in E
bin x, forall e in E
constr x_{12} + x_{13} = 1
constr x_{24} - x_{12} - x_{32} = 0
constr x_{32} + x_{34} - x_{13} = 0
constr x_{24} + x_{34} = 1
min sum_{e in E}{d_{e} * x_{e}}
end

import elytica
def main():
  elytica.init_model("sp")
  elytica.run_model("sp")
  for i in [12,13,32,24,34]:
    print("x"+str(i), "=", elytica.get_variable_value("sp", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("sp"))
  return 0

Mastery variant

Different edge costs on the same network. Which path wins now?

model sp_v
set E = {12, 13, 32, 24, 34}
const d = {6, 3, 2, 4, 8}, forall e in E
bin x, forall e in E
constr x_{12} + x_{13} = 1
constr x_{24} - x_{12} - x_{32} = 0
constr x_{32} + x_{34} - x_{13} = 0
constr x_{24} + x_{34} = 1
min sum_{e in E}{d_{e} * x_{e}}
end

import elytica
def main():
  elytica.init_model("sp_v")
  elytica.run_model("sp_v")
  for i in [12,13,32,24,34]:
    print("x"+str(i), "=", elytica.get_variable_value("sp_v", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("sp_v"))
  return 0

Read this through MCP: read with path: "lessons/sp-conservation", or resource hlpl://lessons/sp-conservation.