Shreyas Bhowmik In this paper, we compare the strength of alternate formulations (polyhedra) of the binary knapsack set. We introduce a specific class of knapsack sets for which we prove that the polyhedra based on their minimal cover inequalities (together with the bounds on the variables) are strictly contained inside the polyhedra defined by their continuous knapsack … Read more
In this paper, we propose an extension of the classical weight reduction inequalities for the binary knapsack polytope for settings where the maximum-weight item in the associated pack is not unique. We derive sufficient conditions under which the extended inequalities are facet-defining and identify conditions under which they strictly dominate the original weight reduction inequalities. … Read more
We introduce a new class of valid inequalities for any 0/1 knapsack polytope, called Solitary item inequality, which are facet-defining. We prove that any facet-defining inequality of a 0/1 knapsack polytope with nonnegative integral coefficients and right hand side 1 belongs to this class, and hence, the set of facet-defining inequalities corresponding to strong covers … Read more