# Multi-commodity flow
#
# Routes several commodities across one network where arcs are shared. The
# bundle constraint is what destroys total unimodularity: each commodity
# alone would be integral, but together they can force fractional extreme
# points, which is why indivisible commodities need integer variables here
# and not in single-commodity flow.
#
# Technique: One flow variable per (commodity, arc) with per-commodity
# balance rows and a shared bundle capacity coupling them.
#
# On this instance the optimum is 14 (minimisation), confirmed
# independently by two phase simplex before publication.
#
# Reference: Ford, L. R. and Fulkerson, D. R. (1958). A suggested
# computation for maximal multi-commodity network flows. Management Science
# 5(1), 97–101. doi:10.1287/mnsc.5.1.97
model m
set V = {1, 2, 3, 4}
set A = {1, 2, 3, 4, 5}
set K = {1, 2}
set outA(V) = outArcs()
set inA(V) = inArcs()
const c = {5, 2, 5, 3, 5}, forall a in A
const u = {2, 4, 5, 5, 4}, forall a in A
const b = {{1, 0, 0, -1}, {1, 0, 0, -1}}, forall k in K, forall v in V
var 0 <= f <= infty, forall k in K, forall a in A
min sum_{k in K}{sum_{a in A}{c_{a} * f_{k,a}}}
# each commodity conserves independently
constr sum_{a in outA(v)}{f_{k,a}} - sum_{a in inA(v)}{f_{k,a}} = b_{k,v}, forall k in K, forall v in V
# but they share the arc capacity -- this is the coupling that breaks TU
constr sum_{k in K}{f_{k,a}} <= u_{a}, forall a in A
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/multicommodity-flow", or resource hlpl://formulations/multicommodity-flow.