Cover Inequalities for Knapsack-Type Constraints

A knapsack constraint is a single linear inequality on binary variables of the form

$$\sum_{j=1}^n a_j x_j \leq b,$$

where $a_j > 0$, $b > 0$, and each $x_j \in \{0,1\}$. The name comes from the 0-1 knapsack problem: $a_j$ is the weight of item $j$, $b$ is the capacity, and $x_j$ indicates whether item $j$ is packed.

A cover for this constraint is a subset $C \subseteq \{1, 2, \ldots, n\}$ whose total weight exceeds the capacity:

$$\sum_{j \in C} a_j > b.$$

In words, $C$ is a cover if packing every item in $C$ would overflow the knapsack — so no feasible 0-1 solution can have $x_j = 1$ for every $j \in C$.

For example, consider the constraint $3x_1 + 4x_2 + 5x_3 + 6x_4 \leq 9$. The set $C = \{2,3,4\}$ is a cover, since

$$a_2 + a_3 + a_4 = 4 + 5 + 6 = 15 > 9.$$