When does linking disjunctive blocks preserve exactness?

Strong formulations for assignment and network design often split each capacitated

resource into one copy per level, the number of items it serves, and

then link the levels of different resources. We ask when linking disjunctive

blocks preserves exactness, which of their levels must be exact, and how the

answer depends on the structure of the coupling. The linked formulation is

ideal if and only if the links are integral when items, weights and capacities

are ignored, and each block is exact at the levels the links actually allow.

Sufficiency follows from disjunctive programming; necessity holds exactly for

the levels used by an admissible profile, so links can exclude a bad level but

never repair one they admit. Our main result characterizes when the formulation

is sharp, that is, exact in the original variables. Integral links are then

not needed: it suffices that they spread each resource’s level distribution, in

the convex order, around an admissible one, and this criterion is correct precisely

when the level capacities satisfy a midpoint inequality, which tightened

capacities can violate. Links are integral on forests and oriented sublattices;

for a count relation an arc-flow network describes them, and a shortest path

in it shows how cut-set inequalities designed for Steiner arborescences can

cut off optimal solutions in unsplittable network design.

Article

Download

View PDF