In TeaUnn/knapsack: the knapsack package

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

library(knapsack)

The knapsack problem

The knapsack problem is a discrete optimization problem where we have a knapsack that can take a limited weight W and we want to fill this knapsack with a number of items i = 1, ..., n, each with a weight w[i] and a value v[i]. The goal is to find the knapsack with the largest value of the elements added to the knapsack.

Brute force search

The only solution that is guaranteed to give a correct answer in all situations for the knapsack problem is using brute-force search, i.e. going through all possible alternatives and return the maximum value found. This can be done using the brute_force_knapsack() function.

# creating the knapsack
set.seed(42)
n <- 2000
knapsack_objects <- data.frame(w = sample(1:4000, size = n, replace = TRUE), 
                               v = runif(n = n, 0, 10000))

brute_force_knapsack(x = knapsack_objects[1:8, ], W = 3500)
brute_force_knapsack(x = knapsack_objects[1:12,], W = 3500)
brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000)
brute_force_knapsack(x = knapsack_objects[1:12,], W = 2000)

Note that the examples only evaluates maximum 12 knapsack objects. This is because the calculation quickly gets very heavy. The algorithm evaluates all possible combinations. The number of possible combinations is two to the power of the number of knapsack objects, so for a knapsack of size 12 there are 2^12 = 4096 different combinations to be evaluated. Running the code with x = knapsack_objects[1:16, ] took 130 seconds for the authors, however with x = knapsack_objects[1:17, ] this time increased to 13 minutes.

Greedy heuristic

Another approach is to use a heuristic or approximation for the problem. This algorithm will not give an exact result (but it can be shown that it will return at least 50 % of the true maximum value), but it will reduce the computational complexity considerably. This is done with the greedy_knapsack() function.

greedy_knapsack(x = knapsack_objects[1:800,], W = 3500)
greedy_knapsack(x = knapsack_objects[1:1200,], W = 2000)

This algorithm is substantially faster to run, compared to the brute force approach. For the authors, testing the algorithm with one million knapsack objects took only about a second.

Profile your code and optimize your code

In the creating of the knapsack package, we the creators have done our best to optimize the code. We have used package profvis to identify bottlenecks and done our best to remove them. However we in no way claim to have written the optimal code, even though we have done our best to get there. This means that performance gains can still be reached by working more on the code. By getting the code more optimized, more objects could be evaluated in less time when searching for the optimal knapsack. Getting the code even more optimized could mean that the time presented for evaluating the algorithm in the brute force method (and the greedy approach) could be decreased, making the function useful for bigger sets of knapsack objects.

TeaUnn/knapsack documentation built on April 3, 2022, 12:02 a.m.