0-1 Knapsack – Optimization Online

Weight reduction inequalities revisited

Published: 2025/12/18, Updated: 2026/02/03

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

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

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