# Knapsack Constraint

Is the following expression a knapsack constraint?

$$\sum_i a(i) y(i) \ge W$$, where $$y(i)$$ binaries, $$a(i),W$$ reals.

What confuses me is the $$\ge$$ sign.

Alternatively, do solvers generate cuts out of this expression?

• If you compliment the variables $y(i)=1-z(i)$, substitute, and rearrange terms, you get a classic knapsack constraint. And yes, solvers generally separate cuts from all available structures.
– Sune
Apr 22 at 21:14

If you complement the variables $$y_i=1−z_i$$, substitute, and rearrange terms, you get a classic knapsack constraint. And yes, solvers generally separate cuts from all available structures.
A simple set of valid inequalities (which could be used as cuts) for your “inverted knapsack constraint” are the so-called knapsack cover inequalities: $$\sum_{i\in N\setminus S}\min \left\{ a_i, W-\sum_{i\in S}a_i\right\}y_i\geq W-\sum_{i\in S}a_i$$ Here $$N$$ is the index set for the variables, and $$S\subseteq N$$ is such that $$\sum_{i\in S}a_i. In “Lifting the Knapsack Cover Inequalities for the Knapsack Polytope” Letchford and Souli show how to strengthen these inequalities through lifting.
Either you are looking at knapsack cover ($$a_i(1-y)_i$$ where $$y_i=0$$) inequality or its part of minimizing knapsack problem. Modern solvers will relax the MIP and then may apply cuts like Gomory cuts.