0-1 Knapsack – Optimization Online

Weight reduction inequalities revisited

Published: 2025/12/18

0-1 Programming 0-1 Knapsack, convex hull, facets, knapsack polytope, Weight division inequalities

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 … Read more

Facets from solitary items for the 0/1 knapsack polytope

Published: 2024/09/24, Updated: 2024/09/26

Shreyas Bhowmik

Sachin Jayaswal

0-1 Programming 0-1 Knapsack, convex hull, facets, knapsack polytope, Solitary item inequalities

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