On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity constraints, and nodal roles. To systematically investigate the effect of commodity-demand heterogeneity (CDH) on computational methods, we propose three distinct integer partitioning schemes: Uniform, characterized by homogeneous distributions; Spread, introducing high heterogeneity; and Beta-Binomial, whose concentration parameter controls the CDH. Central to this approach is the definition of the (relative) Single-Multi-Commodity Gap, (r)SMCG, a novel metric that quantifies the divergence in optimal objective values arising from this lifting process, complemented by a formal measure of CDH. Numerical experiments demonstrate that CDH systematically influences the $\mathrm{SMCG}$ and affects solver behavior, establishing it as a relevant feature of multicommodity flow instances.

Article

Download

View PDF