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 of cardinality 2 is its special case. Next, we provide a counterexample to show that Theorem 6.2 in [13], which claims to provide the complete characterization of the convex hull of a special type of 0/1 knapsack set, called a graphic knapsack set, is invalid. Furthermore, we define a subset of the graphic knapsack set, for which the above theorem becomes valid. We also show that the convex hull of another subset of the graphic knapsack set for which Theorem 6.2 in [13] is invalid, is completely characterized by Solitary item inequalities, along with the trivial nonnegative inequalities.
Article
View Facets from solitary items for the 0/1 knapsack polytope