HLPL / VerTeX Modelling Language Documentation

← formulations

# Minimum-cost network flow
#
# Routes supply to demand at least cost. This generalises transportation,
# transshipment and shortest path — each is this model with a particular
# supply vector and network shape. The node-arc incidence matrix is totally
# unimodular, so with integer supplies and capacities the LP optimum is
# already integral and no integer variables are needed.
#
# Technique: Node balance with arc capacities: outflow − inflow = supply at
#            every node, flow bounded by capacity on every arc.
#
# On this instance the optimum is 36 (minimisation), confirmed
# independently by two phase simplex before publication.
#
# Reference: Ford, L. R. and Fulkerson, D. R. (1962). Flows in Networks.
# Princeton University Press. doi:10.1515/9781400875184
model m
set V = {1, 2, 3, 4}
set A = {1, 2, 3, 4, 5}
set outA(V) = outArcs()
set inA(V) = inArcs()
const c = {8, 1, 6, 6, 7}, forall a in A
const u = {4, 4, 4, 2, 1}, forall a in A
const b = {3, 0, 0, -3}, forall v in V

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

min sum_{a in A}{c_{a} * f_{a}}

constr f_{a} <= u_{a}, forall a in A
constr sum_{a in outA(v)}{f_{a}} - sum_{a in inA(v)}{f_{a}} = b_{v}, forall v in V
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/min-cost-flow", or resource hlpl://formulations/min-cost-flow.