Small extended formulations for group-constrained flows and cographic integer hulls

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 the previous O(n^Δ) bound for fixed Δ. We also show that polynomial dependence on Δ is necessary, up to the exponent. For flows with prescribed supplies and demands, we obtain two further bounds. The first is exponential in the number of supply and demand vertices and polynomial in the binary encoding length of their balances. The second is polynomial in graph size and group order whenever the number of supply vertices is fixed; its inequality count is independent of the demand magnitudes.

Article

Download

View PDF