Network Flow & Min-Cost Flow

TL;DR — Max-flow pushes as much as possible from a source to a sink through capacitated edges; min-cost flow pushes a required amount as cheaply as possible. The reason it matters outside graph theory: any problem shaped like "assign divisible work to time slots, respecting a per-slot capacity and a per-item rate limit, minimising a cost that varies by slot" is a min-cost flow problem, so it has an exact polynomial-time optimum instead of a heuristic. Deferrable-load scheduling is exactly that shape — provided the work can be paused and resumed. If each item must run as one unbroken block, the same problem becomes NP-hard.

---

1. Simple explanation

A flow network is a directed graph where every edge has a capacity — the most that can pass through it. You pick a source and a sink and ask one of two questions:

• Max-flow: what's the most I can push from source to sink at once?
• Min-cost flow: every edge also has a cost per unit. I must push a required amount — what's the cheapest way?

The second question is the useful one, and it's useful because of a trick: a lot of assignment problems don't look like graphs until you draw them as one. Once you do, you get an exact optimum for free from a standard algorithm, instead of inventing a heuristic and hoping.

Analogy — a warehouse loading dock.

You have 30 pallets to load, twelve hours to do it, and a single forklift crew that can move at most 150 kg per hour. Every hour has a different overtime rate. Pallets can be loaded in pieces — half now, half later.

Draw it: the source holds all the work, one node per pallet, one node per hour, and the sink. An edge from a pallet to an hour exists only if that pallet is allowed to be loaded in that hour, and its capacity is how fast one pallet can move. Each hour connects to the sink with capacity 150 — the crew's limit. Put the overtime rate on the pallet→hour edges as the cost.

Now run min-cost flow. The answer it returns is the cheapest loading schedule. You didn't design a scheduling rule; you described the constraints and let the algorithm find the optimum.

The catch, and it's the whole catch: this works because a pallet can be split across hours. If each pallet had to be loaded in one continuous stretch, the network model breaks and the problem becomes genuinely hard (§3.6).

---

2. Diagram

  THE SCHEDULING NETWORK
  ======================

     capacity = E_j            capacity = rate_j          capacity = M
     cost = 0                  cost = cost(t)             cost = 0
                                                                     
              ┌──────► job A ──────┬──────► hour 0 ──────┐
              │                     ├──────► hour 1 ──────┤
   SOURCE ────┼──────► job B ──────┼──────► hour 2 ──────┼────► SINK
              │                     ├──────► hour 3 ──────┤
              └──────► job C ──────┴──────► hour 4 ──────┘

    ▲ how much             ▲ an edge exists ONLY        ▲ per-hour shared
    energy each            for hours inside that        capacity (the
    job needs              job's [earliest, deadline)   transformer limit)

  flow on edge (job j, hour t)  =  units of work given to job j during hour t
  total cost of the flow        =  Σ_j Σ_t  cost(t) · flow(j,t)      ← minimised


  WHY THE THREE EDGE TYPES ARE EXACTLY THE THREE CONSTRAINTS
  ----------------------------------------------------------
    source → job    capacity E_j       "job j must receive E_j units"
    job → hour      capacity rate_j    "job j can't go faster than rate_j"
    hour → sink     capacity M         "no hour may exceed the shared cap M"
    edge exists?    window membership  "no work outside [earliest, deadline)"

  Saturate every source→job edge and you have delivered all the work.
  If max-flow < Σ E_j, the instance is INFEASIBLE — flow tells you that too.

---

3. How it works

3.1 Max-flow: augmenting paths and the residual graph

The core idea is embarrassingly simple:

1. Find any path from source to sink where every edge still has spare capacity.
2. Push as much as that path's tightest edge allows.
3. Repeat until no such path exists.

The subtlety is step 1's bookkeeping. When you push f units along an edge, you also add a reverse edge of capacity f. That reverse edge lets a later iteration undo part of an earlier decision — which is what makes the greedy loop provably reach the true maximum rather than getting stuck. The graph with these leftover capacities is the residual graph.

• Ford–Fulkerson — pick any augmenting path. Correct, but can be slow with awkward capacities.
• Edmonds–Karp — always pick the shortest augmenting path (BFS). O(V·E²).
• Dinic's — build level graphs, push blocking flows. O(V²·E), and much faster in practice.

3.2 Max-flow min-cut (one paragraph, because it's asked constantly)

A cut splits the nodes into a source side and a sink side; its capacity is the total capacity of edges crossing forward. Max-flow = min-cut. Intuition: flow can never exceed any cut (everything must cross it), and when the algorithm halts, the set of nodes still reachable in the residual graph forms a cut whose every crossing edge is saturated — so that cut's capacity equals the flow. This is why max-flow answers "where is the bottleneck?", not just "how much fits."

3.3 Min-cost flow: successive shortest paths

Now each edge carries a cost per unit. Same loop, one change: instead of any augmenting path, always take the cheapest one (shortest path by cost, not by hop count).

  while flow is still needed:
      find the minimum-COST path from source to sink in the residual graph
      push as much as that path allows
      accumulate  pushed_units × path_cost

Reverse edges get negative cost (−cost), because undoing a unit refunds what it cost. Negative edges rule out plain Dijkstra, so you use Bellman-Ford/SPFA, or Dijkstra with Johnson potentials to keep the reduced costs non-negative. Each iteration saturates at least one edge, so it terminates.

Why "cheapest path first" gives a global optimum: after each augmentation the flow is optimal for the amount pushed so far, and the residual graph contains no negative-cost cycle. A flow is minimum-cost exactly when its residual graph has no negative cycle — so maintaining that invariant at every step yields the optimum at the end.

3.4 The reduction that matters

Any problem with this shape is min-cost flow:

Deferrable electricity loads fit line for line: energy needed, charger kW rating, the [plug-in, deadline) window, the hourly price or carbon intensity, and the transformer limit. Same for assigning shifts to workers, bandwidth to transfers, or orders to machine-hours.

3.5 Integrality — why you get whole answers

Min-cost flow is a linear program, and LPs generally return fractions. Flow networks don't: if all capacities are integers, an optimal integral flow exists and the standard algorithms find it. The constraint matrix of a flow problem is totally unimodular, which forces the LP's vertices to be integral.

Practical consequence: you can model "whole kWh" or "whole minutes" and trust the answer, without adding integer variables and without an ILP solver. This is precisely the property that makes the splittable case easy and the non-splittable case hard.

3.6 The boundary: where this stops working

The middle row is the sweet spot. The third row loses it because "one contiguous block" is not expressible as edge capacities — it's a combinatorial choice of start time, which is what pushes you into integer programming.

So the modelling question comes before the algorithm question: can the work be paused and resumed? EV charging, water heating, thermal storage, and most batch computation with checkpointing: yes. A continuous industrial process you cannot interrupt mid-run: no.

---

4. The math

4.1 The linear program

Let x[j][t] be the units of work given to item j in slot t:

  minimise     Σ_j Σ_t  cost(t) · x[j][t]

  subject to   Σ_t x[j][t]  =  E_j          for every item j     (deliver all work)
               0 ≤ x[j][t]  ≤  rate_j       for every j, t       (speed limit)
               x[j][t]      =  0            if t ∉ window_j      (feasible slots)
               Σ_j x[j][t]  ≤  M            for every slot t     (shared capacity)

Note what is not a variable: the total amount of work. Σ_j E_j is fixed by the first constraint, so the optimiser can only change when work happens, never how much. Every unit of cost saved is a timing win.

4.2 A closed form to test your solver against

If all items share one identical window of W slots and there are no per-item rate limits that bind, the optimum collapses to something you can compute by hand. With total work E and cap M, you must occupy

  R = E / M          slots at full capacity

and you should obviously pick the R cheapest slots:

  optimum = M · Σ  cost(t)      over the R cheapest slots
  and you can only ever avoid the (W − R) most expensive slots

Use this as a unit test. If your flow solver disagrees with this on a homogeneous instance, the solver is wrong. §5 asserts it.

Read the second line as an upper bound on ambition: a tight cap forces you to occupy most of the window regardless, so more spare capacity means more savings, because it lets you concentrate the work into fewer, cheaper slots.

4.3 Complexity

For the scheduling network with n items and T slots: V = n + T + 2 and E ≤ n·T + n + T. A year of hourly slots (T = 8760) with a few hundred items is comfortably small.

4.4 Worked example — a 30-van depot

Twelve overnight hours, carbon intensity in gCO₂/kWh:

  hour:  0    1    2    3    4    5    6    7    8    9   10   11
  CI:  350  330  300  250  120   90   70   60   55   60   80  150
       └──── dirty evening ────┘└─────────── clean night ───────────┘

30 vans · 40 kWh each · 11 kW chargers · all parked the whole window · transformer cap M = 150 kW.

  E = 30 × 40 = 1200 kWh          R = 1200 / 150 = 8 of the 12 hours must be used

  carbon-blind (fill earliest hours first):   235,500 gCO2
  min-cost flow optimum:                      102,750 gCO2
  closed form M · Σ(8 cheapest hours):        102,750 gCO2   ✓ agrees
  savings:                                       56.4%

Same 1200 kWh delivered either way, every van full by morning. The only difference is which eight hours were used.

---

5. Real code

"""Min-cost flow, and the deferrable-load scheduling reduction. No dependencies."""
from collections import deque


class MinCostFlow:
    """Successive shortest paths with SPFA (handles the negative reverse edges)."""

    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.cost = [], [], []
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, cap, cost):
        self.adj[u].append(len(self.to))
        self.to.append(v); self.cap.append(cap); self.cost.append(cost)
        self.adj[v].append(len(self.to))          # reverse edge: 0 capacity, negated cost
        self.to.append(u); self.cap.append(0); self.cost.append(-cost)

    def solve(self, src, snk):
        """Return (total_flow, total_cost) for the max flow of minimum cost."""
        flow, total = 0, 0.0
        while True:
            dist = [float("inf")] * self.n
            dist[src] = 0
            prev_edge = [-1] * self.n
            in_queue = [False] * self.n
            q = deque([src]); in_queue[src] = True
            while q:                                   # SPFA: Bellman-Ford with a queue
                u = q.popleft(); in_queue[u] = False
                for e in self.adj[u]:
                    v = self.to[e]
                    if self.cap[e] > 0 and dist[u] + self.cost[e] < dist[v] - 1e-12:
                        dist[v] = dist[u] + self.cost[e]
                        prev_edge[v] = e
                        if not in_queue[v]:
                            q.append(v); in_queue[v] = True
            if dist[snk] == float("inf"):
                return flow, total                     # sink unreachable: done
            push = float("inf")                        # widen along the cheapest path
            v = snk
            while v != src:
                e = prev_edge[v]
                push = min(push, self.cap[e])
                v = self.to[e ^ 1]                     # e^1 is the paired reverse edge
            v = snk
            while v != src:
                e = prev_edge[v]
                self.cap[e] -= push
                self.cap[e ^ 1] += push
                v = self.to[e ^ 1]
            flow += push
            total += push * dist[snk]


def schedule(jobs, cost_per_slot, cap):
    """jobs: (name, energy, max_rate, earliest, deadline). Returns (delivered, cost)."""
    n_jobs, n_slots = len(jobs), len(cost_per_slot)
    src, snk = 0, 1 + n_jobs + n_slots
    g = MinCostFlow(snk + 1)
    for j, (_, energy, rate, earliest, deadline) in enumerate(jobs):
        g.add_edge(src, 1 + j, energy, 0)                       # deliver all its energy
        for t in range(earliest, deadline):                     # only inside its window
            g.add_edge(1 + j, 1 + n_jobs + t, rate, cost_per_slot[t])
    for t in range(n_slots):
        g.add_edge(1 + n_jobs + t, snk, cap, 0)                 # shared per-slot cap
    return g.solve(src, snk)


CI = [350, 330, 300, 250, 120, 90, 70, 60, 55, 60, 80, 150]   # gCO2/kWh, 12 night hours

if __name__ == "__main__":
    vans = [(f"van{i}", 40, 11, 0, 12) for i in range(30)]     # 40 kWh each, 11 kW
    M = 150                                                     # transformer limit, kW
    delivered, optimal = schedule(vans, CI, M)

    energy = sum(v[1] for v in vans)
    slots_needed = energy // M
    closed_form = M * sum(sorted(CI)[:slots_needed])           # the §4.2 unit test
    assert delivered == energy, "some energy was not delivered"
    assert abs(optimal - closed_form) < 1e-6, "solver disagrees with the closed form"

    naive, remaining = 0.0, energy                             # carbon-blind: earliest first
    for t in range(len(CI)):
        take = min(M, remaining)
        naive += take * CI[t]
        remaining -= take
        if remaining == 0:
            break

    print(f"energy delivered   {delivered} kWh (identical in both schedules)")
    print(f"must occupy        {slots_needed} of {len(CI)} hours at the {M} kW cap")
    print(f"carbon-blind       {naive:>10,.0f} gCO2")
    print(f"min-cost flow      {optimal:>10,.0f} gCO2   (= closed form, asserted)")
    print(f"savings            {(naive - optimal) / naive * 100:>9.1f}%")

# Output:
#   energy delivered   1200 kWh (identical in both schedules)
#   must occupy        8 of 12 hours at the 150 kW cap
#   carbon-blind          235,500 gCO2
#   min-cost flow         102,750 gCO2   (= closed form, asserted)
#   savings                  56.4%

In production, don't hand-roll this — networkx.min_cost_flow or OR-Tools SimpleMinCostFlow are faster and battle-tested. Write the loop once to understand the residual graph, then use a library.

---

6. Real-world example

Where the reduction earns its keep — and a trap it exposes.

A depot scheduler was built as a per-vehicle rule: for each van in turn, pour its energy into the cheapest hours still available. Simple, fast, obviously sensible. It also silently loses work.

Take two jobs, three hours at cost [10, 20, 100], cap 10/hour. Job X needs 20 units and may use all three hours; job Y needs 10 and may only use hours 0–1. Both have one hour of slack, so the ordering is a coin flip:

  greedy, X first:  X takes hours 0,1 (the two cheapest) → Y has no capacity left
                    delivered 20/30   cost   300   ← looks GREAT, did less work
  greedy, Y first:  Y takes hour 0, X takes hours 1,2
                    delivered 30/30   cost 1,300
  min-cost flow:    delivered 30/30   cost 1,300   ← always finds a feasible optimum

Two lessons, and the second is the important one:

1. Per-item greedy can strand an item that a different order would have served. Flow either delivers everything or proves it's impossible.
2. A cheaper total that delivered less work is not an improvement. The greedy run reported 300 against flow's 1,300 and looked like a 77% saving — while failing to charge a van. Whenever you compare two schedulers, verify they delivered the same work first; otherwise the comparison is meaningless.

That second point bites in benchmarking generally: if your baseline and your optimiser mark different items infeasible, compare only over the set both of them served.

---

7. Interview questions companies actually ask

Q1. What does the max-flow min-cut theorem say, and why is it useful? Max-flow equals the capacity of the minimum cut. Useful because it converts "how much fits?" into "where is the bottleneck?" — the min cut names the saturated edges limiting throughput. Proof sketch: flow ≤ any cut trivially; at termination the residual-reachable set is a cut whose forward edges are all saturated, so flow = that cut.

Q2. Why do residual/reverse edges exist? They let later augmentations partially undo earlier ones. Without them the greedy path-picking can wedge in a local optimum; with them, "no augmenting path remains" genuinely implies maximum flow.

Q3. How does min-cost flow differ from max-flow, algorithmically? Choose the cheapest augmenting path rather than any/shortest-hop path. Reverse edges take negative cost, so use Bellman-Ford/SPFA or Dijkstra with potentials. Optimality invariant: a flow is minimum-cost iff its residual graph has no negative-cost cycle.

Q4. Recognise this as flow: assign n divisible tasks to T time slots, each task has a deadline window and a rate cap, each slot has a shared capacity, cost varies by slot. Minimise cost. Source→task (capacity = work required), task→slot (capacity = rate, cost = slot cost, edge exists only inside the window), slot→sink (capacity = shared cap). Min-cost flow gives the exact optimum in polynomial time. If max-flow < total work required, it's infeasible.

Q5. Why don't you need an ILP solver here? Flow constraint matrices are totally unimodular, so the LP optimum is integral when capacities are integral. You get whole-unit answers without integer variables.

Q6. What breaks if each task must run as one contiguous block? Contiguity isn't an edge capacity — it's a choice of start time — so the flow model no longer applies and the problem becomes NP-hard. Use ILP/CP for exact answers on small instances, or a heuristic (e.g. least-slack-first) with the flow relaxation as a lower bound.

Q7. Bipartite matching as flow? Source→left (capacity 1), left→right for each allowed pair (capacity 1), right→sink (capacity 1). Max-flow = maximum matching. Add per-pair costs and min-cost flow gives the assignment problem — same thing the Hungarian algorithm solves.

Q8. Complexity, and what makes it fast in practice? Edmonds–Karp O(V·E²), Dinic's O(V²·E), SSP with potentials O(F·E log V). In practice the graphs are sparse and structured (here it's bipartite with a small slot count), and using potentials + Dijkstra avoids repeated Bellman-Ford passes.

Q9. How would you sanity-check a min-cost flow implementation? Construct a degenerate instance with a closed form — e.g. all items sharing one window, no binding rate limits, so the optimum is cap × sum of the R cheapest slot costs with R = total/cap — and assert equality. Also assert the flow saturates every source edge, or the instance was infeasible.

Q10. You have a greedy heuristic and a flow optimum. How do you report the gap honestly? Only after confirming both delivered identical work — a heuristic that strands items can post a lower cost while doing less. And if the heuristic assumes contiguous blocks while the flow allows splitting, the gap conflates heuristic vs exact with contiguous vs splittable; make the two comparable before quoting a number.

---

8. When to use / tradeoffs

Reach for min-cost flow when:

• Work is divisible, or pausable and resumable.
• Constraints are all "how much can pass through here" — amounts, rates, shared caps, allowed pairings.
• You want a provable optimum, or a lower bound to measure a heuristic against.
• You need to know whether the instance is feasible at all.

Don't, when:

Honest limits. Flow gives the optimum for the model you wrote down, which is not the same as the optimum for reality. Three things routinely make the model optimistic: it assumes the cost vector is known exactly in advance (a forecast is not), it assumes splitting is free when each pause/resume may have a real cost, and it assumes the shared cap is the only coupling between items. Quote the result as "the ceiling under these assumptions," not "the achievable saving."

---

9. Summary + related articles

• Max-flow = push as much as possible through capacitated edges; max-flow = min-cut locates the bottleneck. Residual/reverse edges are what make the greedy loop provably optimal.
• Min-cost flow = same loop, always taking the cheapest augmenting path. Optimal iff no negative-cost residual cycle.
• The reduction to remember: amount → source edges, rate limit → middle edges, allowed slots → which middle edges exist, shared capacity → sink edges, slot cost → cost on middle edges.
• Integrality is free — totally unimodular constraints mean integer capacities give integer optima, no ILP needed.
• Divisible work + shared capacity → polynomial and exact. Contiguous blocks + shared capacity → NP-hard. Ask "can it be paused?" before choosing an algorithm.
• Test against the closed form cap × Σ(R cheapest slots), R = total/cap. And never compare two schedulers that delivered different amounts of work.

Related:

• Greedy Scheduling & Interval Selection — the heuristic this gives an exact bound for
• Graphs — BFS/DFS and shortest paths, the machinery underneath
• CPU Scheduling Algorithms — why work-conserving schedulers can't solve this
• Scheduling Under a Time-Varying Cost Signal — the system-design framing
• Carbon-Aware Scheduling of Flexible Loads — where the slot cost is grid carbon intensity
• Complexity Analysis — the bounds quoted in §4.3

Resources

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), Ch. 26 "Maximum Flow" (Ford–Fulkerson, Edmonds–Karp, max-flow min-cut).
• Ahuja, Magnanti, Orlin — Network Flows: Theory, Algorithms, and Applications — the standard reference for min-cost flow and its reductions.
• Kleinberg & Tardos — Algorithm Design, Ch. 7 "Network Flow" (modelling section is especially good on recognising the reduction).
• networkx.min_cost_flow — https://networkx.org/documentation/stable/reference/algorithms/flow.html
• OR-Tools SimpleMinCostFlow — https://developers.google.com/optimization/flow/mincostflow
• LeetCode-adjacent practice: maximum bipartite matching, task assignment — https://cp-algorithms.com/graph/min_cost_flow.html