Straddles and the Dantzig–Wolfe Bound of Cardinality-Indexed Knapsack Formulations

Many integer programs assign indivisible items to capacitated resources, each contributing

a knapsack constraint with a setup variable. Cardinality-indexed formulations copy the

variables of each resource once for every number of items it may serve; they have been used for

generalized assignment, concentrator location, capacitated Steiner arborescence and unsplittable

network design. We characterize when their linear relaxation is exact. The relaxation of a resource

equals its integer hull if and only if the resource has no straddle, a configuration that describes

the fractional vertices of each fixed-cardinality level; in contrast to indexing by load, none of these

vertices is absorbed when the levels are convexified together. If every resource is straddle-free, the

relaxation attains the Dantzig–Wolfe bound under coupling through aggregated variables, and the

condition is also necessary when the coupling can complete a straddle. With exact level capacities,

a resource is straddle-free if and only if its weights take at most two values or its capacity is extreme

at every level. This can be verified in polynomial time. When straddles occur, the integer hulls of

the levels restore the Dantzig–Wolfe bound; we describe them on principal levels and characterize

which rank-type covers define facets. Computational experiments illustrate the results.

Article

Download

View PDF