ISE 754 (Fall 2026) 4.2 Assignment and Transportation

Overview

Michael G. Kay develops assignment, transportation, and minimum-cost network-flow models as linear programs, showing why LP solvers generally outperform greedy heuristics. He also demonstrates OpenStreetMap routing through Logjam, explains how to validate map data, and shows how capacity bounds and parallel arcs represent practical logistics constraints.

Key takeaways

For the three-car, three-passenger example, greedy matching costs 12 while the optimal LP assignment costs 10; local cheapest choices do not guarantee a globally cheapest assignment.
A transportation tableau is feasible only when total supply is at least total demand, and its greedy solution can still be worse than the LP optimum: 1,030 versus 970 in the example.
OpenStreetMap’s residential-street detail comes with a scale tradeoff: data must be downloaded by bounding box, and route assumptions such as Dan Allen’s weekday closure need external validation.
Minimum-cost network flow represents routing, assignment, and transportation in one framework, with positive supply, negative demand, and zero-balance transshipment nodes.
Flow bounds can enforce operational requirements: requiring one unit on arc 2→3 changes the shortest-path model’s cost from 14 to 18.
Parallel arcs model tiered logistics costs: ship up to 20 units from node 1 to node 4 at cost 6 per unit, then use the more expensive cost-18 option for overflow.

Chapters

0:00 OpenStreetMap Data, Geocoding, and Route Validation

FAF5 provides major truck links directly through Logjam, while OpenStreetMap covers residential streets and must be downloaded for a selected bounding box.
Logjam’s `loc2lonlat` function converts addresses or place names to coordinates; results for broad areas such as Raleigh represent population centroids and carry uncertainty.
A route between Fitts-Woolard Hall and D.H. Hill Library differs between OpenStreetMap data and a server route because the downloaded network does not encode Dan Allen’s weekday car closure.
The Dan Allen route can be valid for buses but not daytime car travel, illustrating why network results need local validation.

6:14 Linear Assignment: Why Greedy Matching Misses the Optimum

The linear assignment problem matches nodes in a bipartite network at minimum total cost; the lecture’s small example assigns three sources to two destinations.
In a three-car, three-passenger example, choosing the lowest remaining travel time greedily produces a total cost of 12, while the optimal LP assignment costs 10.
With 12 cars and 12 passengers, there are 12! possible assignments—about 479 million—yet an LP solver can find the optimum without enumeration.
The Hungarian method was historically useful, but modern LP solvers make specialized algorithms unnecessary for many assignment problems; quadratic assignment is not linear-programmable.

12:42 Transportation Models: Supply, Demand, and Greedy Cost Gaps

Transportation models generalize assignment by allowing each supply node to ship quantities to demand nodes at per-unit costs.
A tableau organizes the three supply nodes, four demand nodes, unit costs, supplies, and demands; feasibility requires total supply to meet or exceed total demand.
The greedy method repeatedly selects the cheapest available cell and allocates as much as possible, removing satisfied demand columns as it proceeds.
For the illustrated example, greedy allocation costs 1,030 versus the LP optimum of 970, showing that network greedy solutions can be materially worse.

17:59 Capacity-Constrained Allocation and Minimum-Cost Network Flow

Transportation modeling captures facility capacity limits that the ALA allocation procedure’s uncapacitated assumption omits; Greensboro’s allocation is split between Raleigh and Charlotte.
Minimum-cost network flow generalizes assignment and transportation by representing supply as positive node values, demand as negative values, and transshipment nodes as zero.
A shortest-path problem can be modeled as one unit of supply at the origin and one unit of demand at the destination, though Dijkstra’s algorithm is more efficient for ordinary shortest paths.
Arc lower and upper bounds encode required or limited flows: forcing one unit across arc 2→3 raises the example’s optimal cost from 14 to 18.

24:35 Multigraph Arcs Model Capacity Tiers and Expedited Shipping

A multigraph permits multiple arcs between the same node pair, allowing different transportation modes or rate tiers to be modeled separately.
For the two arcs from node 1 to node 4, the cheaper arc costs 6 per unit but has a capacity of 20.
Additional flow can use a second, unlimited-capacity arc at cost 18 per unit, representing costly expedited transport or a spot-market shipment.
The minimum-cost solution fills the cheaper capacity first and uses the higher-cost arc only when more flow is required.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Michael G. Kay.