Solving a Knapsack Problem

John Mitchell
November 2010

Consider the knapsack problem

min - 3x1 - 4x2 - 6x3 subject to x1 + 3x2 + 5x3 ≤ 7 xi = 0,1 i = 1, ...,3

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

min - 3x1 - 4x2 - 6x3 subject to x1 + 3x2 + 5x3 ≤ 7 0 ≤ xi ≤ 1 i = 1, ...,3

The simplex tableau for this problem is

x1 x2 x3 s4 s5 s6 s7 |---|-----------------------------| |-0-|--3----4----6---0---0--0---0-| M = | 7 | 1 3 5 1 0 0 0 | | 1 | 1 0 0 0 1 0 0 | | 1 | 0 1 0 0 0 1 0 | | 1 | 0 0 1 0 0 0 1 | -----------------------------------

The optimal tableau for this relaxation is

|-----|x1--x2--x3-----s4----s5-----s6--s7-| |10.6-|-0---0---0----1.2---1.8----0.4---0-| 1 | 0.6 | 0 0 1 0.2 - 0.2 - 0.6 0 | M = | 1 | 1 0 0 0 1 0 0 | | | | | 1 | 0 1 0 0 0 1 0 | --0.4---0---0---0----0.2---0.2----0.6---1-|

Thus, the optimal solution to the initial relaxation is

x1 = 1, x2 = 1, x3 = 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

x2 + x3 ≤ 1

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

x x x s s s s s |-----|-1---2---3------4-----5------6---7---8| |10.6-|-0---0---0----1.2---1.8----0.4---0--0-| | 0.6 | 0 0 1 0.2 - 0.2 - 0.6 0 0 | M 2 = | 1 | 1 0 0 0 1 0 0 0 | | 1 | 0 1 0 0 0 1 0 0 | | 0.4 | 0 0 0 - 0.2 0.2 0.6 1 0 | | | | ----1---0---1---1------0-----0------0---0--1--

Pivoting to get an identity, we obtain

-------x1--x2--x3-----s4-----s5----s6--s7--s8-- |10.6 | 0 0 0 1.2 1.8 0.4 0 0 | |-----|---------------------------------------| 3 | 0.6 | 0 0 1 0.2 - 0.2 - 0.6 0 0 | M = | 1 | 1 0 0 0 1 0 0 0 | | 1 | 0 1 0 0 0 1 0 0 | | 0.4 | 0 0 0 - 0.2 0.2 0.6 1 0 | |- 0.6| 0 0 0 - 0.2 0.2 - 0.4 0 1 | -----------------------------------------------

Solving this tableau using the dual simplex method gives

x x x s s s s s |---|-1----2---3---4----5--6---7----8-| |-9-|-0----2---0---0---3---0---0----6-| | 1 | 0 0 1 0 0 0 0 1 | M 3 = | 1 | 1 0 0 0 1 0 0 0 | | 1 | 0 - 2 0 1 - 1 0 0 - 5 | | | | | 0 | 0 - 1 0 0 0 0 1 - 1 | --1---0----1---0---0---0---1---0----0--

So, the solution to the modified relaxation is

x1 = 1, x2 = 0, x3 = 1

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