Multi-Commodity Flow Model¶
Formal model family — instantiates Network Flow Optimization
Represents several distinct flow classes over one shared network — each with its own sources and sinks — coupled only where they compete for the same edge capacity.
Some networks carry not one flow but several at once, each with its own origins, destinations, and identity, all contending for the same links. Multi-Commodity Flow Model is the model family for that situation. Each commodity — a distinct class of flow that cannot be substituted for another — is conserved separately and moves between its own sources and sinks, but the commodities are bound together by a single fact: on any shared edge, the sum of all commodities using it cannot exceed that edge's capacity. Its defining idea is precisely this coupling. Because the commodities compete for shared capacity, you cannot route each one on its own and staple the answers together; you have to solve them jointly, and that joint constraint is what makes the model both necessary and hard.
Example¶
A national rail network carries three commodities over largely shared track: heavy unit trains of coal running from mines to a port, intermodal container trains running between inland terminals, and intercity passenger services. Each has entirely different origin-destination pairs and its own conservation — a coal train is not interchangeable with a passenger service — yet on the single-track segments through a mountain pass, all three compete for the same slots.
Modeled separately, each looks feasible. Modeled jointly, the coupling constraint on the shared segments bites: schedule enough coal capacity through the pass and there is no room left for the passenger timetable. The model surfaces the contention that per-commodity planning hid, and points to the real fix — a passing siding that adds capacity on exactly the coupled segment, or an explicit split of that capacity among the three classes. The insight comes only from representing the commodities together on the edges they share.
How it works¶
The model family is organized around per-commodity flow tied by shared-edge constraints:
- Define the commodities. Each class of flow is a separate unit with its own conservation and its own source-sink pairs; the number and granularity of commodities is a modeling choice, not a given.
- Bundle on shared edges. For every edge, the sum of all commodities routed over it must respect one capacity — the coupling constraint that distinguishes this model from several independent flows.
- Solve jointly. Because the coupling ties the commodities, the routing is found together, often via decomposition techniques such as column generation or Lagrangian relaxation that exploit the near-separable structure.
- Expose the contention. The solution shows where commodities crowd each other out, which is the whole reason to model them on one network rather than many.
Tuning parameters¶
- Commodity granularity — how finely flow is split into classes. More commodities capture real distinctions but enlarge the model sharply and can make it intractable.
- Shared vs. dedicated capacity — whether edges are pooled across commodities or partitioned per class. Pooling is efficient; partitioning is predictable and protects each commodity's reserved share.
- Splittability — whether a single commodity may be spread across multiple paths or must follow one. Allowing splits eases feasibility but complicates the solution and its operability.
- Fairness vs. efficiency — how contested capacity is shared when not all commodities can be fully served; the choice decides which class yields.
When it helps, and when it misleads¶
Its strength is representing genuine contention: when heterogeneous classes truly compete for the same links, only a joint model reveals that relieving one starves another, and only a joint model can allocate the shared capacity deliberately. Treating the network as a single aggregate flow, or as several independent ones, hides exactly the interaction that matters.
Its failure modes are computational and representational. Integer multi-commodity flow — insisting each commodity follow whole paths — is NP-hard, so realistic instances can become intractable as commodities multiply.[1] A commodity explosion, splitting flow into too many classes, buys detail at ruinous cost, while collapsing classes that genuinely differ erases the contention the model exists to show. The discipline is to model only the commodities that actually compete on shared edges, use the coarsest split that preserves the real interaction, and lean on decomposition rather than brute force.
How it implements the components¶
Multi-Commodity Flow Model fills the multiple-class, shared-capacity side of the archetype — the part no single-flow method reaches:
flow_unit_definition— it defines several distinct commodity classes, each a separately conserved unit; this multiplicity is the model's reason for existing.source_and_sink_definition— each commodity carries its own source-sink pairs, so origins and destinations are per class rather than global.edge_capacity— the shared edge capacity is the coupling constraint that binds the commodities, limiting their summed flow on every common link.
It does not minimize a single cost_or_throughput_objective to optimality across the network — that framing is Min-Cost Flow Model's — nor locate a single-flow bottleneck_monitor min-cut like Max-Flow Analysis; and it sets no live priority_class_rule routing policy, which is Data Network Routing Policy's.
Related¶
- Instantiates: Network Flow Optimization — it extends the archetype to the case where several irreducible flow classes share one constrained network.
- Sibling mechanisms: Max-Flow Analysis · Min-Cost Flow Model · Data Network Routing Policy · Patient Flow Pathway Review · Traffic Assignment Model · Logistics Routing Plan · Network Capacity Dashboard
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Multi-Commodity Flow Model operates as a computation, comparison, model, or analytic representation used to infer, estimate, or choose because it represents several distinct flow classes over one shared network — each with its own sources and sinks — coupled only where they compete for the same edge capacity.
Independent corroboration: The frozen evidence defines Multi-Commodity Flow Model as 'Represents several distinct flow classes over one shared network — each with its own sources and sinks — coupled only where they compete for the same edge capacity', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Single lineage
Present-day reach: Multi-domain
Rationale: Multicommodity flow is a named network-optimization model family from operations research.
Related originating lineages:
- Computer Science & Software Engineering — Algorithm design developed complexity and approximation methods for these models.
- Mathematics — Graph theory and linear programming provide the formal foundations.
Review resolution: Both independent reviews agree on primary origin operations_research; reconciliation resolves secondary fields (domain_reach_disagreement). Alternate origins retained (computer_science, mathematics) are the union of reviewer-supported formative lineages with explicit rationales, not a list of later application domains. Present-day breadth is represented separately as domain_reach=multi_domain; origin_mode=single_lineage records the historical relationship among lineages. Confidence is conservatively reconciled to high, and encyclopedia_synthesis=false preserves either reviewer's finding that the encyclopedia generalized the mechanism.
Review outcome: Reconciled after independent review; high confidence.
References¶
[1] Whereas fractional multi-commodity flow is solvable in polynomial time, the integral version — routing each commodity along whole paths — was shown NP-complete for as few as two commodities (Even, Itai & Shamir, 1976). This is why realistic integer instances demand decomposition and careful commodity granularity rather than direct solution. withdrawn registry ↩