In SimonJonsson/lab6: LAB6 different knapsack solutions

library(lab6)
devtools::install_github("hadley/lineprof")
library(lineprof)
set.seed(42)
m <- 2000
knapsack_objects <-
  data.frame(w = sample(1:4000, size = m, replace = TRUE),
             v = runif(n = m, 0, 10000))

Introduction

In this lab we implement different solutions for the 0/1-knapsack- and unbounded knapsack problem. We have implemented both a parallel and non-parallel brute force solution, a dynamic programming solution and a solution using the greedy heuristic. We have documented the runtimes and the profiling of each solution.

Runtime of codes

Bruteforce knapsack solution

Parallel

system.time(brute_force_knapsack(x = knapsack_objects[1:20,], W = 3500, parallel=FALSE))

Non-parallel

system.time(brute_force_knapsack(x = knapsack_objects[1:20,], W = 3500, parallel=FALSE))

Dynamic knapsack solution

system.time(knapsack_dynamic(x = knapsack_objects[1:500,], W = 3500))

Greedy knapsack solution

system.time(greedy_knapsack(x = knapsack_objects[1:1000000,], W = 3500))

Profiling

devtools::install_github("hadley/lineprof")
library(lineprof)

Bruteforce knapsack solution

Parallel

lineprof(brute_force_knapsack(x = knapsack_objects[1:12,], W = 3500, parallel=TRUE))

All segments of the code are in similar timesteps - quite tricky to identify bottlenecks. However one could look over using some primitive functions instead of using lapply to find the row with near-optimal value. A suggestions might be using max().

Non-parallel

lineprof(brute_force_knapsack(x = knapsack_objects[1:12,], W = 3500, parallel=FALSE))

The lapply function might be exchanged with using a max() primitive. Generating the matrix with given parameters: weight and val one could use max to find the maximum val given that the weight $\leq$ W.

Dynamic knapsack solution

lineprof(knapsack_dynamic(x = knapsack_objects[1:100,], W = 3500))

Here we identify that the segment in the code that takes most time to run is the replicate function. This could be handled by some other primitive, or maybe the pre-allocation can be circumvented by having dynamic size of the vector.

Greedy knapsack solution

lineprof(greedy_knapsack(x = knapsack_objects[1:20000,], W = 3500))

Not alot to improve on here.

Parallelizing brute force knapsack

The performance that could be gained is non-existent since the lapply used doesn't contain any calculations. So there is little to no sequential computations that are done. If we had a computationally heavy lapply segment then we could gain an decrease in computation time.

SimonJonsson/lab6 documentation built on May 7, 2019, 2:53 a.m.