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

662 Views Asked by At

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?

1

There are 1 best solutions below

1
On

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'$

For many combinatorial optimisation problems, studying the polytope of the problem (that is finding valid inequalities and facets) is a kind of "sport" (see http://integer.tepper.cmu.edu/webpub/integerRioMPSjuly.pdf which explains it pretty well). For the knapsack, though, I think mostly gomory-chvatal cuts are used, and not much else.