4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – Septimus G Sep 29 '16 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.