Transshipment: least-cost flow through a network, and modelling a warehouse's throughput limit

The data in this project is synthetic — a shipping network (plants, warehouses, regions, lane costs and capacities) generated locally by data/make_data.py. That is deliberate: grading needs a known least-cost flow to measure against, and real lane-cost/capacity data is confidential. No signup, no GPU.

Before you start

New to network flow? Start here.

A transshipment network moves goods from supply points (plants) through intermediate transshipment points (warehouses / distribution centres) to demand points (regions). Every lane (an arc) has a per-unit cost and a capacity (max units it can carry). The min-cost flow problem asks: how do you move every unit from plants to regions, obeying every capacity, at the lowest total cost?

Two ideas make it click:

It’s not “each region buys from the cheapest plant.” That greedy plan usually pushes more through one plant or lane than it can supply/carry — it’s cheap-looking but infeasible. The solver finds the cheapest plan that actually ships.
The math is a linear program with a special structure, and libraries solve it exactly and fast. You’ll use networkx, which wants each node’s net demand (negative for supply, positive for demand, zero for a pass-through warehouse) and each arc’s weight (cost) and capacity.

Part A models and solves the network. Part B adds a limit that doesn’t fit the standard tool: a cap on how much can flow through a warehouse (a node capacity, not an arc capacity). Solvers cap arcs, not nodes — so you’ll learn the standard trick, node-splitting, to express it. What you’ll learn is in Section 3.

New to Python too? See Start Here — it starts from zero, and shows how to run this in your browser with nothing to install.

1. The Brief

A manufacturer ships from a few plants, through regional distribution centres, to demand regions. Part A: model the network and solve for the least-cost shipping plan, and see why the “everyone buys from the cheapest plant” instinct produces a plan that can’t actually be shipped. Part B: the DCs now have throughput limits — a warehouse can only handle so many units a day — and the cheapest plan from Part A overloads one of them. You’ll model that node limit correctly (node-splitting) and re-solve.

Min-cost flow is one of the most useful models in operations: distribution planning, production scheduling, assignment, even image segmentation reduce to it. The transshipment version — supply, demand, and pass-through nodes with capacities — is the backbone of network distribution planning, and node capacities are where a textbook model meets a real warehouse.

2. Difficulty & time

Difficulty 7 / 10. You model a real optimisation problem (get the supply/demand signs and the arc attributes right), reason about feasibility versus cost, and then apply a non-obvious modelling transformation (node-splitting) to express a constraint the library can’t take directly. The debug surface is large: a wrong sign or an unbalanced supply/demand makes the solver reject the problem outright. Calibrated against the ledger (G10): it sits above the difficulty-6 band — warehouse-sim (6), delivery-routing (6), fraud-rings (6) — in the 7–8 tier (a non-obvious algorithmic/modelling choice, per the rubric), because the node-split reformulation is a genuine insight, not a parameter change. It’s the first difficulty-7 in the ledger.

Time is separate from difficulty: Part A is 60–90 minutes; Part B is 3–4 hours. The scripts run in about a second.

3. What you’ll be able to do after

Model a transshipment network in networkx — supply/demand signs, arc costs and capacities — and solve the min-cost flow.
Explain why greedy is infeasible — show that “cheapest plant per region” overshoots supply, and what the optimal flow does instead.
Verify a flow — check conservation at every node (in − out = demand).
Enforce a node capacity by node-splitting — model a warehouse throughput limit that an edge-capacity solver can’t express directly, and re-solve.

The finished result

By the end of Part A you’ll have modelled the shipping network, solved the least-cost flow, and shown why the cheaper-looking greedy plan can’t actually ship:

15 nodes, 44 arcs;  supply 100 == demand 100
min-cost flow:  optimal total cost 7508, carried on just 13 of the 44 lanes
greedy 'cheapest plant per region':  6409 (looks cheaper!) -- but pulls 68 through P1 (supply 35)
                                     and 32 through P2 (supply 25)  ->  over supply, INFEASIBLE
conservation holds at every node: True

The least-cost shippable plan costs 7508; the cheaper-looking 6409 greedy plan overloads two plants and can’t be shipped — the gap between cheap-looking and feasible is the whole point.

4. Prereqs & time box

You can write functions, use dictionaries, and read CSVs with pandas. No optimisation background needed — the orientation and Part A build the model from scratch. You’ll call networkx.min_cost_flow rather than implement the algorithm; the skill is modelling the problem correctly (including the node-split), not coding the simplex method.

Where to write and run code

Two ways to run this project — pick either:

In your browser (no install). If the project page shows a ▶ Run button, click it to run Part A right here — nothing to set up. Part A uses pandas and networkx, which run in the browser.
On your computer. The one-time setup — installing Python, downloading the code from the course site (no GitHub, no git), opening a terminal, creating a virtual environment, installing the requirements, and running Part A step by step — is covered once in Start Here. Come back here once python -c "import networkx" runs without error. Part B (writing your own solution) needs this local setup.

Time box

Part A — Guided Build: 60–90 minutes. Hard cap.
Part B — Your Turn: 3–4 hours. Hard cap.

5. Setup & data

The data is synthetic and generated locally — see the banner above and SOURCES.md for full provenance. One command creates both parts’ data:

python data/make_data.py

That writes eight CSVs into data/ (git-ignored; regenerate anytime, byte-for-byte identical because the seeds are fixed). Per part (a / b):

plants_{}.csv — plant_id, supply
warehouses_{}.csv — warehouse_id (Part B adds throughput_cap)
regions_{}.csv — region_id, demand
arcs_{}.csv — source, target, cost, capacity

Part A is 3 plants / 4 warehouses / 8 regions (supply = demand = 100). Part B is 3 / 4 / 10 (supply = demand = 120) plus a throughput cap on each warehouse. Costs are per-unit; the numbers describe no real company.

6. Part A — Guided Build

You’ll model the network and solve the min-cost flow. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

python part_a/flow.py

Prefer the browser? If this page has a ▶ Run button, click it instead of the command above — Part A runs in your browser with nothing to install. The STEP output and every checkpoint below are identical either way.

The full, commented script is in part_a/flow.py. The spine:

Step 1 — Build the network.

Checkpoint: 15 nodes, 44 arcs; supply 100 = demand 100. Plants carry negative demand, regions positive, warehouses zero. (An unbalanced total has no feasible flow.)

Step 2 — Solve the min-cost flow.

Checkpoint: optimal total cost 7508, carried on just 13 of the 44 arcs.

Step 3 — Why not the cheapest plant? Greedy is infeasible.

Checkpoint: “each region from its cheapest plant” costs 6409 (looks cheaper!) but pulls 68 units from P1 (supply 35) and 32 from P2 (supply 25) — over supply, so the plan can’t ship. The gap between cheap-looking and feasible is the whole point.

Step 4 — Verify flow conservation.

Checkpoint: at every node, inflow − outflow equals its demand — the definition of a valid flow. Writes part_a/flow_a.csv.

Why this and not that

Why min-cost flow, not greedy. Greedy optimises each region in isolation and ignores shared capacity, so it double-books plants and lanes. Min-cost flow optimises the whole network at once and only ever returns a shippable plan.
Why the sign convention. networkx encodes supply as negative demand so one number per node captures both; getting it backwards silently solves a different problem (or is rejected).
Why capacities change the answer. Without capacities the cheapest lanes carry everything; with them, the solver spreads flow onto costlier lanes exactly where a cheap one is full — which is what makes the result non-obvious.

Functions you’ll meet (and where to read more)

Function	What it does here	Docs
`nx.DiGraph`, `add_node(demand=...)`	Model supply/demand per node	DiGraph
`nx.min_cost_flow`	Solve for the least-cost flow	min_cost_flow
`nx.cost_of_flow`	Total cost of a flow	cost_of_flow
`G.predecessors` / `successors`	Sum in/out flow to verify conservation	DiGraph.predecessors

If something looks off

The greedy plan (6409) prints as cheaper than the “optimal” flow (7508) — did the solver get it backwards? No, and your run is correct: that contrast is the entire point of Step 3. The 6409 plan is infeasible — it funnels 68 units through P1 (supply 35) and 32 through P2 (supply 25), so it can’t actually be shipped. min_cost_flow returns the cheapest plan that does ship, which by definition costs more than an impossible one. A feasible answer costing more than an infeasible one is expected here, not a bug.
A checkpoint number doesn’t match. The data is seeded, so the numbers are exact. Re-run python data/make_data.py (you may have skipped or edited it), then re-run Part A.
Setup problems (Python not found, pip, FileNotFoundError, re-activating the venv): see the troubleshooting list in Start Here.

7. Part B — Your Turn

Part B is the optional “your turn” half — a guided fill-in-the-blank, not a blank page. You get a working starter (part_b/starter.py) that already handles the easy version; your job is to finish the # TODO it marks out. More open than Part A’s step-by-step, but you are never staring at an empty file. If you finished Part A and want to prove the skill, this is where it happens. New to Python? It’s completely fine to stop after Part A and come back later.

Same core skill — min-cost flow — but the warehouses now have throughput caps (warehouses_b.csv, throughput_cap): a limit on how much can flow through each DC, on a new, larger network. Find the least-cost flow that respects the arc capacities and every warehouse’s throughput cap.

The catch: min_cost_flow caps edges, not nodes. If you just build the Part A model on this network (ignoring the caps), the optimal flow shoves too much through one warehouse — the starter does exactly this and its plan overloads a DC, so it’s infeasible and scores 0. The fix is the standard node-split: replace each warehouse w with two nodes w_in → w_out joined by an edge whose capacity is the throughput cap; route all inbound lanes into w_in and all outbound lanes out of w_out. Now the node limit is an edge the solver understands.

The transfer: Part A’s model has no node capacities at all, so it can’t be reused as-is — the capacity-respecting solution needs the reformulation, not a parameter tweak.

Reference rule (reproduce it to match the yardstick)

Node-split every warehouse (w_in, w_out, edge capacity = throughput_cap), rebuild the plant → w_in and w_out → region arcs with their original costs and capacities, solve min_cost_flow, then translate the flow back onto the original arcs (plant → warehouse, warehouse → region) for your output.

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

flow.csv — columns source, target, flow on the original arcs (plant → warehouse and warehouse → region).
report.json — with keys total_cost, achieved_metric (you can leave achieved_metric null; the grader scores you).

Then:

python part_b/starter.py
pytest part_b/test_solution.py -q

If pytest reports everything as skipped, it just means the output files don’t exist yet — run python part_b/starter.py first (once your solution fills in the TODOs), then re-run.

You’re done when the tests pass. The score is 0 if the flow is infeasible (conservation broken, an arc over capacity, a warehouse over its throughput cap, or demand unmet), otherwise reference_cost / your_cost, and you need ≥ 0.98 (the reference reaches 1.00). The edge-only plan is infeasible (a warehouse over cap) → 0.

Constraints — what must be true of your solution, not how to get there

No warehouse’s total throughput exceeds its throughput_cap.
No arc carries more than its capacity; flow conserves at every node.
Every region’s demand is met exactly; plants ship no more than their supply.
Report flow on the original arcs, not the split-node arcs.

Hints

Hint 1 — why the edge-only model fails

Run Part A’s model on this network and check how much flows into each warehouse. One DC’s inflow exceeds its throughput_cap — the cheapest routing wants to funnel everything through it. Edge capacities can’t stop that, because the limit is on the node, not any single lane.

Hint 2 — the node-split

Replace warehouse w with w_in and w_out and one edge w_in → w_out whose capacity is the throughput cap and weight 0. Every plant → w arc becomes plant → w_in; every w → region arc becomes w_out → region. All flow through w must now cross the capped middle edge.

Hint 3 — translate back

After solving the split graph, the flow on plant → w_in is the flow on the original plant → w arc, and w_out → region is the original w → region. Drop the internal w_in → w_out edge from your output — the grader wants the original arcs.

8. Self-check

You don’t need the answer key. You’re done when all of these hold:

pytest passes — feasible (every warehouse within its throughput cap) and within 2% of the reference cost.
Your total cost is higher than Part A-style edge-only cost on this network — respecting the node cap forces some flow onto costlier lanes. If it equals the edge-only cost, you didn’t enforce the cap.
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: sum the flow into each warehouse and compare to its throughput_cap. The binding one should sit exactly at its cap; if any is over, the node-split didn’t take.

9. Stretch

Shadow prices. Which warehouse cap is binding, and what would one more unit of its throughput save? Loosen the binding cap by 1 and re-solve to read the marginal value.
Add direct lanes. Allow a few plant → region arcs (bypassing the DCs) and see when the optimum uses them.
(Genuinely hard) Fixed costs to open a lane. Give each arc a fixed cost to use it at all (not just per-unit). That breaks the pure-flow LP into a mixed-integer problem — the start of network design, and a cousin of the facility-location project in this batch.

10. Ship it

Put this in a portfolio repo and it counts. In that repo’s README:

State the finding in one sentence a planner gets: “the least-cost shipping plan costs 7508; respecting a warehouse throughput limit reroutes flow onto costlier lanes for a small premium, and a greedy cheapest-plant plan is infeasible.”
Show the network with flows, and the before/after when the warehouse cap binds.
Include the node-split diagram and one paragraph on why node capacities need it. That paragraph is what signals you understand flow modelling, not just an API call.

Keep make_data.py and the tests in the repo so anyone can reproduce your numbers from zero.

11. Sources

Rendered from SOURCES.md.

Field	Value
Dataset	Synthetic distribution network (Part A 3 plants/4 DCs/8 regions; Part B 3/4/10 with warehouse throughput caps) — supply, demand, arc costs and capacities
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seeds `20260756` (A) and `20260757` (B)
Source URL	Not applicable — generated, not fetched
License	Not applicable — synthetic, no third-party rights
Access / generation date	2026-07-18
Redistribution	Permitted — synthetic; output regenerated from the seeded script, never committed
robots.txt checked	Not applicable — no scraping
ToS URL	Not applicable — no external source

Synthetic data teaches the mechanic; it does not prove a finding about the real world. The network was generated on purpose — the min-cost-flow and node-split techniques are the point, not a claim about any real distribution network.

Next up

That’s the top of the Supply Chain track. Browse all courses → to pick your next build.