Transport problem¶
An optimization problem that allocates or couples supply at source locations with demand at destination locations while minimizing total transport cost under mass-balance or assignment constraints.
Core Idea¶
The transport problem asks how to move or couple a source distribution to a target distribution at minimum total cost. A plan specifies how much of each source goes to each destination, respects supply and demand, and is scored by the cost assigned to every source–destination transfer. Monge's original form uses a map and does not split source mass; Kantorovich's relaxation uses a coupling and can divide it.
Scope of Application¶
Use transport problem when the two mass distributions, feasibility constraints, cost function, and minimization target are explicit. Use transport problem when the two mass distributions, feasibility constraints, cost function, and minimization target are explicit.
- Logistics. Allocates shipments to destinations.
- Resource allocation. Matches supply and demand.
- Probability. Couples distributions.
- Economics. Studies allocation under costs.
- Optimal transport geometry. Defines distances through minimum coupling cost.
Clarity¶
Physical travel is not required: source and target may be probability distributions or abstract states. Conversely, an ordinary routing problem is not automatically transport because vehicles and path order may be the decision instead of mass coupling. The closest near miss sets the boundary: The assignment problem is closest: it is a discrete one-to-one special case with indivisible equal units, while transport allows mass splitting in its broader formulations.
Manages Complexity¶
Separating supply, demand, plan, cost, and objective exposes changes such as unbalanced mass, capacity constraints, indivisibility, regularization, and nonunique optima without losing the basic problem. The central Monge determinism–Kantorovich splitting tradeoff is this: A map preserves source identity while a coupling gives convex flexibility. A second cost realism–mathematical tractability tension matters because Rich constraints model logistics better but can obscure the core coupling geometry.
Abstract Reasoning¶
Use three linked moves: define source and target measures or finite quantities; check that total mass balances or model the mismatch explicitly; write admissible maps or couplings. As a collapse test, the case exits when no source-target mass balance, coupling decision, or aggregate transport-cost objective remains. A fourth check is to specify the per-unit cost and aggregate objective.
Knowledge Transfer¶
Minimum-cost coupling transfers to image matching, probability, and economics, but the source-target mass constraint distinguishes transport from generic optimization. The nearest stopping boundary is explicit: The assignment problem is closest: it is a discrete one-to-one special case with indivisible equal units, while transport allows mass splitting in its broader formulations. The inclusion test remains: A problem is a transport problem when source mass, target mass, admissible couplings, and a transport cost are specified and total cost is minimized subject to balance constraints. The structure no longer applies when the case exits when no source-target mass balance, coupling decision, or aggregate transport-cost objective remains. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. Feasible plans are ranked by total cost.
Relationships to Other Abstractions¶
Current abstraction Transport problem Domain-specific
Parents (1) — more general patterns this builds on
-
Transport problem is a kind of, typical Minimum-cost flow problem Domain-specific
The classical (Hitchcock-Koopmans) transport problem is a bipartite instance of minimum-cost flow: route supply to demand across a capacitated bipartite network while minimizing total transfer cost.
Hierarchy path (1) — routes to 1 parentless root
- Transport problem → Minimum-cost flow problem → Optimization
Neighborhood in Abstraction Space¶
Transport problem sits in a moderately populated region (55th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Stowage plan for container ships — 0.86
- Individual-Pieces Set — 0.86
- Draft survey — 0.86
- Fuel Fraction — 0.85
- Business performance management — 0.85
Computed from structural-signature embeddings · 2026-10-08