A cardinality-indexed extended formulation with valid inequalities for unsplittable multicommodity network design

We study the unsplittable multicommodity fixed-charge network design problem, in which

every commodity follows a single path and each arc is installed at most once. Its linear relaxation

is weak because a commodity may occupy a fraction of an arc. We propose an extended

formulation that indexes the variables of each arc by the number of commodities it carries.

Its relaxation is at least as strong as that of a compact formulation with cardinality bounds

and lifted capacities, and can be strictly stronger. The convex hull of the single-arc relaxation

decomposes by level and projects onto the compact single-arc closure; level counterparts of

cover, configuration, k-split c-strong and packing inequalities are never weaker than the classical

ones, and level-aware cut-set inequalities exploit the extended space beyond that closure. Level

windows and a bound-preserving reduction keep the model small. The root bound improves on

the best published bound for 27 of the 31 Canad instances and equals it on the other four. On 40

random instances the approach proves optimality for 39 against 32 for the compact formulation,

with search trees 2–6 times smaller. An ablation shows that exact per-level separation and the

level-aware cut-set inequalities carry the bound.

Article

Download

View PDF