HLPL / VerTeX Modelling Language Documentation

← formulations

# Maximum flow
#
# Pushes as much as possible from source to sink. By max-flow min-cut the
# optimum equals the capacity of the lightest cut separating them, which is
# the LP dual of this program — the reference here checks the primal value
# against enumeration of every cut.
#
# Technique: Maximise the flow leaving the source subject to node balance
#            at every intermediate node and arc capacities.
#
# On this instance the optimum is 5 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Ford, L. R. and Fulkerson, D. R. (1956). Maximal flow through a
# network. Canadian Journal of Mathematics 8, 399–404.
# doi:10.4153/CJM-1956-045-5
model m
set V = {1, 2, 3, 4}
set Mid = {2, 3}
set A = {1, 2, 3, 4, 5}
set outA(V) = outArcs()
set inA(V) = inArcs()
const u = {3, 2, 1, 6, 2}, forall a in A

var 0 <= f <= infty, forall a in A

max sum_{a in outA(1)}{f_{a}}

constr f_{a} <= u_{a}, forall a in A
# only the intermediate nodes must balance; source and sink are free
constr sum_{a in outA(v)}{f_{a}} - sum_{a in inA(v)}{f_{a}} = 0, forall v in Mid
end

import elytica

def outArcs():
  return {1: [1, 2], 2: [3, 4], 3: [5], 4: []}
def inArcs():
  return {1: [], 2: [1], 3: [2, 3], 4: [4, 5]}

Read this through MCP: read with path: "formulations/max-flow", or resource hlpl://formulations/max-flow.