# Transshipment
#
# Ships from plants to markets through intermediate warehouses. The only
# structural difference from transportation is the presence of nodes whose
# balance is zero: they neither produce nor consume, they relay. Still
# totally unimodular, so still integral without integer variables.
#
# Technique: Node balance where intermediate nodes have zero supply, so
# flow passes through rather than originating or terminating.
#
# On this instance the optimum is 20 (minimisation), confirmed
# independently by two phase simplex before publication.
#
# Reference: Orden, A. (1956). The transhipment problem. Management Science
# 2(3), 276–285. doi:10.1287/mnsc.2.3.276
model m
set V = {1, 2, 3, 4, 5}
set P = {1, 2}
set W = {3}
set M = {4, 5}
set A = {1, 2, 3, 4}
set outA(V) = outArcs()
set inA(V) = inArcs()
const c = {4, 5, 8, 3}, forall a in A
const s = 1
const d = {1, 1}, forall k in M
var 0 <= f <= infty, forall a in A
min sum_{a in A}{c_{a} * f_{a}}
# plants ship no more than they hold
constr sum_{a in outA(p)}{f_{a}} <= s, forall p in P
# warehouses relay: whatever arrives leaves again
constr sum_{a in outA(w)}{f_{a}} - sum_{a in inA(w)}{f_{a}} = 0, forall w in W
# markets receive their demand
constr sum_{a in inA(k)}{f_{a}} >= d_{k}, forall k in M
end
import elytica
def outArcs():
return {1: [1], 2: [2], 3: [3, 4], 4: [], 5: []}
def inArcs():
return {1: [], 2: [], 3: [1, 2], 4: [3], 5: [4]}
Read this through MCP: read with path: "formulations/transshipment", or resource hlpl://formulations/transshipment.