Record number :
884209
Title of article :
Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation Original Research Article
Author/Authors :
Yves Pochet، نويسنده , , Laurence A. Wolsey، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1995
Pages :
18
From page :
57
To page :
74
Abstract :
Three 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.
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics
Serial Year :
1995
Link To Document :
بازگشت