Find optimal Solution to Knapsack Problem with Linear Programming in R

In another post I demonstrated how to develop a heuristic to solve the knapsack problem. We managed to solve the problem quite well and had an optimality gap of about 1%, that is, our solution was 1% away from the optimal solution.

Here I’d like to demonstrate, how simple it is to solve the Knapsack Problem using Integer Linear Programming (ILP).

If you have never heard about that technique, read about it somewhere. It’s worth it. I may make a post about these basics later sometime.

We again use the same problem instance as described in file ‘KS_P08.txt’, which can be downloaded here. The format is again as follows:

• Number of objects (n)
• Total capacity of Knapsack
• The weight of the n objects
• An empty line
• The value of the n objects

What is the objective?

Of course the objective in the Knapsack Problem is to pack the knapsack in a way, that the resulting value is maximized but the capacity (weight) limit isn’t exceeded.

What are our Decision Variables?

The simplest and also intuitive selection for the decision variables would be to assign a binary variable to each object at disposal. If it’s 1, the object is packed, 0 else. So the solution will be a sequence of zeroes and ones, indicating which items to pack into the knapsack.

What Constraints do we have?

This question, too, can be answered very quickly. In this problem we do only have one constraint, the knapsack’s capacity limit, which may not be exceeded.

That’s it! We’re done. The rest is only craftmanship you’ve to become familiar with, but the brainwork is done with the considerations made above. Let’s now start the implementation in R and use the open lp-solver lpSolve:

library(lpSolve)

knapsack_ilp <- function(knapsack, capacity) {
  lpmod <- list(
    # objective function (maximize value)
    obj = knapsack$value,
    # constraints sum of weights < capacity
    con = matrix(knapsack$weight,
      nrow = 1,
      byrow = T
    ),
    # signs
    dir = c("<="),
    # 'right hand side' der Ungl.
    rhs = capacity,
    # enumerate binary decision variables  
    binary.vec = 1:nrow(knapsack)
  )
    lsg <-
      lpSolve::lp("max",
                  lpmod$obj,
                  lpmod$con,
                  lpmod$dir,
                  lpmod$rhs,
                  binary.vec = lpmod$binary.vec)
    
    return (lsg)
}
          
# load knapsack instance KSP8
dat <- read.table(file = "KS_P08.txt")
n <- dat[1,1]
capacity <- dat[2,1]
weights <- dat[3:(n+2),1]
values <- dat[(n+3):nrow(dat),1]

knapsack <- data.frame(item_id=1:n, weight=weights, value=values)

# solve it: ILP
a <- knapsack_ilp(knapsack = knapsack, capacity = capacity)
print(a)
print(a$solution)

At the bottom we prepare a dataframe from the knapsack instance file, containing all information about the problem. The work is done in the function knapsack_ilp, where the Integer Linear Programming model is generated. It’s just syntax and nothing special. Run the command ‘?lpSolve::lp’ in the R-Console to get a description on the lp-command of the lpSolve package:

Now as the last step we can now execute our script and solve the LP. It will produce the following output:

> source('C:/Users/fabian.leuthold/Downloads/knapsack_ilp.R')
Success: the objective function is 13549094 
 [1] 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1

When we compare it with the known optimum we realize we have found the (an) optimal solution!