Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 ยท Network Flows

Network Flow Models

Learn network flow modelling: nodes, arcs, supply and demand, flow balance, minimum-cost flow, transshipment, and why network LPs always have integer solutions.

Many real problems are about moving something through a network: trucks on roads, packets on links, water in pipes, money between accounts. A network flow model is a linear program with a special and beautiful structure. It is easy to formulate, fast to solve, and, unlike general integer programs, it automatically returns whole-number answers when the data are whole numbers.

This lesson introduces the vocabulary and the most general model, minimum-cost flow. The rest of the chapter (shortest paths, maximum flow, transportation and assignment) are all special cases.

Anatomy of a network

  • A node (vertex) is a place: a factory, warehouse, intersection or router.
  • An arc (edge) (i, j) is a directed link from i to j. It may have a cost c_ij per unit of flow and a capacity u_ij (maximum flow) and a lower bound l_ij (often 0).
  • Each node has a net supply b_i: positive for sources (supply), negative for sinks (demand), zero for transshipment nodes.
  • The decision variable x_ij is the flow on arc (i, j).

The minimum-cost flow problem sends supplies to demands at least cost:

TEXT
minimize    sum c_ij x_ij
subject to  sum_j x_ij  -  sum_k x_ki  =  b_i      for every node i   (flow balance)
            l_ij <= x_ij <= u_ij                  for every arc

The balance equation reads: flow out minus flow in equals the node's net supply. For the whole network to be feasible, total supply must equal total demand (sum b_i = 0). If it does not, add a dummy node.

flowchart LR
    A["A (supply 20)"] -->|"cost 2, cap 15"| C["C"]
    A -->|"cost 4, cap 10"| B["B"]
    B -->|"cost 1, cap 10"| C
    C -->|"cost 3, cap 25"| D["D (demand 20)"]
    B -->|"cost 6, cap 8"| D

Each arc is labeled with cost per unit and capacity. Node A must send 20 units to D by any route.

Solving with linprog

The balance equations have a neat matrix form. The node-arc incidence matrix N has one row per node and one column per arc; the column of arc (i, j) has +1 in row i and -1 in row j. Then flow balance is N x = b.

Python Minimum-cost flow on the network above

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how the cheap route A to C (cost 2) fills to its capacity of 15, and the remaining 5 units go through B. The sum 15 + 5 leaving A equals the supply 20, and the arcs into D carry exactly 20.

One balance equation is always redundant: the rows of N sum to zero, so if all but one balance equations hold, the last holds automatically. Solvers handle this without trouble.

Special cases of min-cost flow

Problem Network structure
Shortest path Send 1 unit from source to target, arcs uncapacitated
Maximum flow Add a return arc from sink to source with cost -1 (or maximize its flow)
Transportation Bipartite: supply nodes connected to demand nodes
Assignment Transportation with all supplies and demands equal to 1
Transshipment Supply, demand and intermediate nodes

Learning one model therefore gives you five. Each gets its own lesson: Shortest Paths as Flows, Max Flow and Min Cut, The Transportation Problem and The Assignment Problem.

Why the answers are integers

A matrix is totally unimodular (TU) when every square submatrix has determinant 0, 1 or -1. The incidence matrix of a directed graph is TU. For an LP with a TU constraint matrix and integer right-hand sides, every vertex of the feasible region is an integer point (by Cramer's rule). The simplex method moves between vertices, so it returns an integer solution without any branch and bound.

That is a big deal: it means fractional shipments never occur, and large flow problems (millions of arcs) solve quickly with specialized network simplex codes.

Python Integer data in, integer flow out

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every feasible instance returns an integer flow. Contrast this with the knapsack in Integer Programming Basics, where the LP solution was fractional.

Modeling extensions

  • Lower bounds. Set l_ij > 0 to require minimum flow, for example a contractual minimum shipment.
  • Multiple sources and sinks. Just give several nodes nonzero supply; or add a super-source and super-sink connected to them.
  • Node capacities. Split a node into in and out copies connected by an arc with the node's capacity.
  • Gains and losses. When flow is multiplied along an arc (currency conversion, leakage), the model becomes a generalized network; the incidence matrix is no longer TU and integers are not guaranteed.
  • Multi-commodity flow. Several different goods share arc capacities. This is a plain LP, but integrality is lost.
  • Time-expanded networks. Copy the network for each period and add holding arcs (i, t) -> (i, t+1) to model inventory or waiting.

If your model looks like "move things between places with capacities and costs", write it as a network flow first. You will get integer answers, fast solves and easy interpretation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the node balance equation say?

    Sources have positive net supply, sinks negative, and transshipment nodes zero, which makes in and out equal there.
  2. 2. What condition must total supply and demand satisfy for a flow to exist?

    Flow is conserved, so the sum of net supplies must be 0.
  3. 3. Why does a min-cost flow LP with integer supplies and capacities have an integer optimal solution?

    Total unimodularity makes all vertices of the feasible region integer points when the right-hand sides are integers.
  4. 4. Which problem is NOT a special case of minimum-cost flow?

    The knapsack constraint matrix is a single dense row, not a network incidence matrix, and its LP relaxation can be fractional.

Summary

  • A network model has nodes with net supply, arcs with costs and capacities, and flow variables.
  • Minimum-cost flow minimizes total cost subject to flow balance and capacity bounds.
  • Shortest path, max flow, transportation and assignment are special cases.
  • The incidence matrix is totally unimodular, so integer data give integer optimal flows.
  • Extensions: lower bounds, node capacities, time-expanded networks; gains and multi-commodity flow lose integrality.

Next: Shortest Paths as Flows