# What formulation for any 0-1 knapsack problem has the tightest LP relaxation?

Since the knapsack problem with integer variables can be reduced to a binary variable case, consider the problem $$\max\{cx:x\in K\}$$ $$K:=\left\{ x\in \{0,1\}^n: \sum_{i=1}^n a_ix_i\le b \right\}$$ Given two different formulations representing the same integer set, K, consider their linear relaxations to be $P_1 \text{ and } P_2$ we say that if $P_1\subset P_2$ then the first formulation is better.

One well known alternative formulation of this problem, is that based on minimal covers, which are sets of objects that cannot fit in the knapsack simultaneously: $$K^C:=\left\{ x\in \{0,1\}^n: \sum_{i\in C} x_i\le |C|-1, \text{for every minimal cover C of K } \right\}$$ However $K^C$ is not always better than $K$.

Does a formulation better than $K$ exist, for any 0-1 knapsack problem?

Many "better relaxation" formulations than the one you have for $K$ exists. For instance, the relaxation of $K' = \big\{ x \in \{0,1\}^n | \sum_{i=1}^n a_ix_i \leq b, \sum_{i \in C} x_i \leq |C|-1 \text{ for every minimal cover C of K} \big\}$
will always be better than the one of $K$ and $K^C$ (it will be the smallest of the two), and $K=K^C=K'$
• $K'$ does not always have a better relaxation than $K$. It will always be better or \textbf{equal} to $K$ and $K^C$. You can show this with a small example. I think the rest of the answer is good, thanks. – Septimus G Sep 29 '16 at 22:15