Pochet, Yves
[UCL]
Wolsey, Laurence
[UCL]
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} where 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 different descriptions of the convex hulls and fast combinatorial algorithms for separation. Some partial results are given for the set Z and another extension.
Bibliographic reference |
Pochet, Yves ; Wolsey, Laurence. Integer Knapsack and Flow Covers With Divisible Coefficients - Polyhedra, Optimization and Separation. In: Discrete Applied Mathematics, Vol. 59, no. 1, p. 57-74 (1995) |
Permanent URL |
http://hdl.handle.net/2078.1/48381 |