MultiCommodity

Multicommodity is a concept in optimization and economics referring to multiple distinct goods or demands that are modeled simultaneously within a single framework. In network optimization, the most studied instantiation is the multicommodity flow problem, where a network is represented as a directed graph with edge capacities, and a set of commodities, each with a specified source and sink and a demand. The goal is to route flows for all commodities through the network without exceeding edge capacities while satisfying conservation laws at intermediate nodes.

Formally, for each edge e and commodity k, let f_e^k denote the amount of commodity k that uses edge e. The capacity constraint requires that for every edge e, the sum over all commodities of f_e^k does not exceed the edge capacity c_e. For each commodity k and each node v, flow conservation requires that the total inflow to v minus the total outflow from v equals zero, except at the source s_k (net supply d_k) and the sink t_k (net demand −d_k). The objective is commonly to maximize the total delivered demand ∑_k d_k, or to minimize costs given nonnegative per-edge costs.

Variants include dynamic or time-expanded networks, stochastic or robust formulations, and cases with different objective functions such as cost minimization, delay minimization, or reliability maximization. The problem generalizes the single-commodity max-flow and is central in transportation, telecommunications, and logistics.

Computationally, the multicommodity flow problem can be formulated as a linear program and solved in polynomial time in theory, but the size grows quickly with the number of commodities. Integral or combinatorial versions are often NP-hard for general networks; practitioners employ decomposition, approximation, and heuristic methods for large-scale instances.