Knapsack

Integer programming is all about formulations. Preferably tight formulations. I will show you here two equivalent formulations of the famous knapsack problem.

Knapsack problem: Given a set of weights of objects, a knapsack of capacity and  values select a subset of objects such that their total weight is less than and the total value is maximized.

Let’s state it in a formal way. Let . We want to solve .  The knapsack problem is of fundamental importance to combinatorial optimization with lots of real world applications.  Consider now the following different formulation. Define to be a cover if . A cover will be called minimal if every proper subset of it is not a cover. In other words, if you remove at least one index (any index will do the work) the corresponding set is a feasible solution. Now define the following set of solutions .  It should be clear that . The following theorem proves that .

Theorem: .

Proof: Suppose .  For the sake of contradiction assume that , i.e., where . Find which is a minimal cover. Clearly, such a set exists. But then which contradicts the fact that $latex x\in K^{C}$. QED

It is really interesting that the LP relaxation of a knapsack problem can be better in the second formulation, despite the fact that there are so many more constraints. However, it is worth noting that the two formulations are not directly comparable. There exist instances where the first is better, where the second is better and where neither is better.