VALID INEQUALITIES FOR 0-1 KNAPSACKS AND MIPS WITH GENERALIZED UPPER BOUND CONSTRAINTS

We derive valid inequalities for the knapsack problem with generalised upper bound (GUB) constraints, and show that the separation problem for a subclass of the inequalities is again a knapsack problem with GUB constraints. It is shown that the inequalities are "strong" by showing that in one special case, they suffice to describe the convex hull of solutions, and for other models it is possible to obtain violated inequalities by using constraint aggregation followed by the above separation procedure. © 1990.