Knapsack formulations

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 \{a_i\}_{i=1,..,n} of n objects, a knapsack of capacity b and  values \{c_i\}_{i=1,..n} select a subset of objects such that their total weight is less than b and the total value is maximized.

Let’s state it in a formal way. Let K=\{x \in \{0,1\}^n:\sum_{i=1}^n a_ix_i \leq b\}. We want to solve \max_{x \in K} \sum_{i=1}^n c_ix_i.  The knapsack problem is of fundamental importance to combinatorial optimization with lots of real world applications.  Consider now the following different formulation. Define C \subset [n] to be a cover if sum_{i \in C} a_i>b. 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 K^{C}=\{x \in \{0,1\}^n:\sum_{i=1}^n a_ix_i \leq b\}.  It should be clear that K \subseteq K^{C}. The following theorem proves that K=K^{C}.

Theorem: K^{C} \subseteq K.

Proof: Suppose x \in K^{C}.  For the sake of contradiction assume that x \notin K, i.e., \sum{i \in J} a_i>b where J=\{i:x_i=1\}. Find J' \subseteq J which is a minimal cover. Clearly, such a set exists. But then \sum_{i \in J'}x_i=|J'| 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: