Solving a Knapsack Problem

Consider the knapsack problem

$$\begin{array}{lrcrcrcl} \min & -3x_1 & - & 4x_2 & - & 6x_3... ...x_3 & \leq & 7 \\ &&& x_i & = & 0,1 && i=1,...,3 \end{array}$$

This is an integer programming problem. We solve it by solving a sequence of linear programming relaxations of the problem. The initial relaxation is

$$\begin{array}{lrcrcrcl} \min & -3x_1 & - & 4x_2 & - & 6x_3... ... & 7 \\ & 0 & \leq & x_i & \leq & 1 && i=1,...,3 \end{array}$$

The simplex tableau for this problem is

$$M = \begin{array}{\vert r\vert rrrrrrr\vert} \multicolumn... ... & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ \hline \end{array}$$

The optimal tableau for this relaxation is

$$M^1 = \begin{array}{\vert r\vert rrrrrrr\vert} \multicolu... ... 0.4 & 0 & 0 & 0 & -0.2 & 0.2 & 0.6 & 1 \\ \hline \end{array}$$

Thus, the optimal solution to the initial relaxation is

$$x_1=1, \quad x_2=1, \quad x_3=0.6$$

This does obviously not solve the original relaxation, because it has x₃=0.6. Notice that no feasible solution to the integer programming problem can have both x₂=1 and x₃=1. Thus, every solution satisfies

$$x_2 + x_3 \leq 1$$

We can add this constraint to M¹, giving the tableau

$$M^2 = \begin{array}{\vert r\vert rrrrrrrr\vert} \multicol... ... \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{array}$$

Pivoting to get an identity, we obtain

$$M^3 = \begin{array}{\vert r\vert rrrrrrrr\vert} \multicol... ...& 0 & 0 & 0 & -0.2 & 0.2 & -0.4 & 0 & 1 \\ \hline \end{array}$$

Solving this tableau using the dual simplex method gives

$$M^3 = \begin{array}{\vert r\vert rrrrrrrr\vert} \multicol... ... \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ \hline \end{array}$$

So, the solution to the modified relaxation is

$$x_1=1, \quad x_2=0, \quad x_3=1$$

This is integral, so it solves the original integer program.