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 … Read more
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 … Read more
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 … Read more
We construct small extended formulations for nonnegative integer flows whose arc labels have a prescribed sum in a finite abelian group. For circulations, the formulation is a single integral network that combines cycles even when they lie in different components. This yields an O(Δn²) bound for strictly Δ-modular cographic integer hulls of translated cones, improving … Read more
We consider the multilinear polytope defined as the convex hull of the feasible region of a linearized binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we refer to as the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, … Read more