Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation

AbstractThree regions arising as surrogates in certain network design problems are the knapsack set X = xϵZn+: ∑nj=1 Cjxj⩾ b, the simple capacitated flow set Y = (y, x) ϵR1+ × Zn+: y ⩽ b, y ⩽ ∑nj=1 CjXj, and the set Z = (y, x) ϵ Rn+ × Zn+: ∑nj=1yj ⩽ b, yj ⩽ Cjxj for j = 1,…,n where the capacity Cj+1 is an integer multiple Cj for all j. We present algorithms for optimization over the sets X and Y, as well as different descriptions of the convex hulls and fast combinatorial algorithms for separation. Some partial results are given for the set Z and another extension