INTEGER KNAPSACK AND FLOW COVERS WITH DIVISIBLE COEFFICIENTS - POLYHEDRA, OPTIMIZATION AND SEPARATION

Three regions arising as surrogates in certain network design problems are the knapsack set X = {x is an element of Z(+)(n): Sigma(j=1n) C(j )x(j) greater than or equal to b}, the simple capacitated flow set Y = {(y,x) is an element of R(+)(1) x Z(+)(n) y less than or equal to b, Y less than or equal to Sigma(j=1)(n) C(j)x(j)}, and the set Z = {(y, x) is an element of R(+)(n) x Z(+)(n): Sigma(j=1)(n) y(j) less than or equal to b, y(j) less than or equal to C(j)x(j) for j = 1,..., n} whe re the capacity C-j+1 is an integer multiple C-j for all j. We present algorithms for optimization over the sets X and Y as well as differen t descriptions of the convex hulls and fast combinatorial algorithms f or separation. Some partial results are given for the set Z and anothe r extension.