flowchart LR
S((Source)) -->|c, u| A((A))
S -->|c, u| B((B))
A -->|c, u| C((C))
B -->|c, u| C
A -->|c, u| T((Sink))
C -->|c, u| T
B -->|c, u| T
25 Network Optimization
25.1 Networks and Network Optimization
A network (or graph) is a set of nodes (vertices) connected by arcs (edges). When arcs carry weights such as distance, time, capacity, or cost, a surprising number of business problems become network-optimisation problems: shortest route, minimum-cost connection, maximum throughput, cheapest shipment, earliest project completion. Many of these problems admit specialised algorithms that are far faster than solving the same problem as a general LP.
NoteWhy network methods beat plain LP here
Problems with a network structure (such as transportation or assignment) have totally unimodular constraint matrices, which means their LP relaxations automatically give integer solutions. Specialised algorithms (Dijkstra, Ford-Fulkerson, Prim, Kruskal) exploit that structure for speed and exactness.
25.2 Representing a Network in R
The igraph package (Csardi and Nepusz 2006) is the standard R workhorse for network analysis. Graphs are typically built from an edge list data frame with vertex attributes and edge weights.
Vertices and edges can be listed and the weighted adjacency matrix extracted for any downstream algorithm. directed = TRUE switches from undirected to directed graphs when arc direction matters (for example, a one-way road network or a precedence diagram).
25.3 Shortest Path
Dijkstra’s algorithm (Dijkstra 1959) finds the shortest path from a source vertex to every other vertex when arc weights are non-negative. For graphs with negative arc weights (rare in business networks but common in economics problems), Bellman-Ford (Bellman 1958) is the safe alternative.
The shortest route from A to E is traced and its total weight returned. distances() gives the all-pairs matrix in one call, which is useful for pre-computing travel times between every pair of depots before a downstream routing model.
25.4 Minimum Spanning Tree
A spanning tree of a connected graph is a subset of arcs that connects every vertex with no cycles. The minimum spanning tree (MST) minimises the total arc weight of that subset. Prim’s algorithm (Prim 1957) grows the tree outward from a starting vertex; Kruskal’s (Kruskal 1956) sorts arcs by weight and adds them if they do not create a cycle. Both return the same MST when arc weights are distinct.
The MST retains four edges and reaches every vertex at minimum total weight. Business uses include laying cable between offices, joining distribution hubs, and designing water-pipe networks where every node must be reached once and only once.
25.5 Maximum Flow
In a directed network each arc has a capacity. The maximum-flow problem asks the largest amount of flow that can be pushed from a source vertex \(s\) to a sink vertex \(t\) subject to arc capacities and conservation at every non-terminal vertex. Ford and Fulkerson (1956) introduced the augmenting-path framework; Edmonds and Karp (1972) showed that using shortest augmenting paths yields polynomial time.
Maximum throughput from S to T is reported along with the flow on every arc. Arcs at capacity (\(flow = cap\)) are the bottlenecks; expanding them is the most direct way to raise throughput.
25.6 Minimum Cost Flow
Minimum-cost flow sends a target quantity through a network at the lowest possible cost subject to arc capacities and conservation. It is a proper generalisation of shortest path (single unit of flow), transportation (bipartite), and max flow (no cost, find the largest quantity). A direct LP formulation with lpSolve works for small problems; dedicated solvers (for example, the network simplex) are used in production.
The optimal flow moves exactly ten units from S to T at minimum cost; per-arc flows are bounded below every capacity. Structure like this is why min-cost flow is the canonical formulation for supply-chain routing when costs, capacities, and balance requirements all matter at once.
25.7 Transportation as Network Flow
The classical transportation problem (Chapter 23) is a min-cost flow on a bipartite network with source-side supply nodes and sink-side demand nodes. Casting it explicitly as a network makes the structure obvious and reuses the same algorithms that solve shortest path and max flow.
Each positive entry of the shipment matrix is a bipartite arc carrying flow; zeros are arcs left unused. Any transportation problem can be solved either with lp.transport as here or by writing the min-cost flow formulation of §6 directly.
25.8 Assignment as Bipartite Matching
The balanced assignment problem is a bipartite matching: one side has \(n\) workers, the other side has \(n\) jobs, every arc from a worker to a job carries a cost. Each worker is assigned to exactly one job and each job to exactly one worker. It is a special case of transportation (supply and demand both equal to one) and admits the Hungarian algorithm (Kuhn 1955), which lp.assign uses.
Every row and column of the solution matrix contains exactly one 1, which is the matching. Unbalanced problems (more workers than jobs or vice versa) are handled by adding a dummy row or column with zero cost before calling lp.assign.
25.9 Critical Path Method
Activity-on-arc project networks place activities on arcs and events (start and end of an activity) on nodes. Given each activity’s duration, the critical path method (Kelley 1961) computes the earliest start and earliest finish of each activity by a forward pass, and the latest start and latest finish by a backward pass from the project finish. Activities whose slack (latest minus earliest) is zero are on the critical path and drive the project duration.
The critical path is the chain of activities with zero slack: any delay on those activities delays the whole project. Stakeholders are usually most interested in (1) the project duration, (2) which activities are critical, and (3) how much float the non-critical activities have.
25.10 Traveling Salesman
The traveling salesman problem asks for the shortest tour that visits every node exactly once and returns to the start. Unlike the problems above, TSP is NP-hard: the number of tours grows factorially with the number of cities, so exact solution quickly becomes intractable. Business practice usually relies on heuristics (nearest-neighbour, 2-opt, Lin-Kernighan) or specialised MIP formulations (Dantzig, Fulkerson and Johnson 1954) with subtour-elimination cuts. Routing problems with time windows and capacity (the vehicle routing problem) extend TSP and form the technical backbone of commercial logistics software.
TipTractable vs intractable network problems
Shortest path, MST, max flow, min-cost flow, transportation, and assignment all have polynomial-time algorithms and scale to hundreds of thousands of nodes. TSP and vehicle routing are NP-hard and need heuristics or commercial solvers beyond a few hundred nodes. The split matters for setting stakeholder expectations early.
25.11 Reporting Network Results
A complete network report states the problem type (shortest path, MST, max flow, min-cost flow, transportation, assignment, CPM), the node and arc definitions with their attributes (weight, capacity, cost, duration), the algorithm used, the optimal plan (the path, the tree, the flow matrix, the assignment, the critical activities), the objective value, and any bottleneck or critical items that drive the result. For large graphs, a summary of which arcs are used at capacity and which vertices remain slack is usually more actionable than the raw solution. Williams (2013) and Hillier and Lieberman (2020) give the classical formulations; Csardi and Nepusz (2006) document igraph.
25.12 Summary
| Concept | Description |
|---|---|
| Foundations | |
| Network definition | Nodes connected by arcs carrying weights, capacities, or costs |
| Representation in igraph | graph_from_data_frame and adjacency matrix for analysis |
| Paths and Trees | |
| Shortest path (Dijkstra) | Source-to-every-node shortest distances for non-negative weights |
| Bellman-Ford for negative weights | Handles negative arc weights that Dijkstra cannot |
| Minimum spanning tree | Cheapest cycle-free subset of arcs reaching every vertex |
| Flows | |
| Maximum flow | Largest throughput from source to sink under arc capacities |
| Minimum cost flow | Cheapest flow that respects capacity and node-balance constraints |
| Transportation as min-cost flow | Bipartite min-cost flow with supplies and demands |
| Bipartite and Projects | |
| Assignment as bipartite match | Bipartite matching solvable via the Hungarian algorithm |
| CPM forward and backward pass | Earliest and latest start and finish times for every activity |
| Critical path and float | Activities with zero slack drive the project duration |
| Edge Cases and Delivery | |
| TSP and vehicle routing | NP-hard tours; require heuristics or specialised solvers |
| Density and algorithm choice | Polynomial methods for sparse networks; heuristics as graphs densify |
| Reporting checklist | Problem type, nodes, arcs, algorithm, plan, objective, bottlenecks |