Weight reduction inequalities revisited

In this paper, we have proposed a strengthening of well known weight reduction inequalities, when the maximum weighted item in the pack is not unique. We provide some sufficient conditions under which these inequalities are facet-defining. Furthermore we provide some conditions under which the strengthened inequality strictly dominates the weight reduction inequality. We also introduce another set of valid inequalities named weight division inequalities to prove that these two classes of valid inequalities, along with the trivial nonnegative inequalities, completely characterize the convex hull of a special class of binary knapsack set, wherein the first few least weighted items have the same weight while the remaining have weights exceeding half the knapsack capacity.

Article

Download

View PDF