Knapsack Constraint

Question

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?

Answer 1

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<W$. In “Lifting the Knapsack Cover Inequalities for the Knapsack Polytope” Letchford and Souli show how to strengthen these inequalities through lifting.

Answer 2

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.