In martynas2514/Lab06: knapsack problem

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

library(Lab06)

This package boasts 3 solutions aimed at resolving the so-called Knapsack problem. It consists in a optimization problem where we have a knapsack that can take a limited weight W and it is necessary to fill it with a number of items i = 1, ..., n, each with a weight W_i and a value V_i. The goal is to fill the knapsack with the largest value of the elements added.

brute_force_knapsack

1. Raw

This solution implemented involves the computation of all possible permutations of objects. Therefore, the best solution is picked out (highest value complying with the maximum weight allowed). This approach is of complexity O(2ⁿ) since all possible combinations 2ⁿ need to be evaluated.

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:16, ], W = 3500)

The following table shows some performance metrics and time to carry out the execution over 16 objects.
Units: milliseconds.

table = cbind(c("min", "lq", "mean", "median", "uq", "max", " neval"), c("328.6047", "380.9232", "412.8512", "409.5157", "436.1366", "566.0723", "100"))

knitr::kable(
  table, caption = 'Performance Metrics',col.names = c("metrics", "value")
)

The mean time of execution is  409.5157 ms

2. After profiling

Lab06::brute_force_knapsack(x = knapsack_objects[1:16, ], W = 3500)

The following table shows some performance metrics and time to carry out the execution over 16 objects after profiling.
Units: milliseconds.

table = cbind(c("min", "lq", "mean", "median", "uq", "max", "neval"), c("227.514", "261.15", "288.3555", "287.9914", "310.0506", "416.5125",   "100"))

knitr::kable(
  table, caption = 'Performance Metrics',col.names = c("metrics", "value")
)

The mean time of execution is 287.9914 ms, which represents an improvement of approximately 30 porcentual points with respect to the raw implementation

3. Parallelization

Parallelization has been implemented in order to improve the performance of the algorithm.

Lab06::brute_force_knapsack(x = knapsack_objects[1:16, ], W = 3500, parallel = TRUE)

The following table shows some performance metrics and time to carry out the execution over 16 objects using parallelization.
Units: milliseconds.

table = cbind(c("min", "lq", "mean", "median", "uq", "max", "neval"), c("622.0385", "822.6735", "874.6833", "873.8708", "920.6959", "1232.251",   "100"))

knitr::kable(
  table, caption = 'Performance Metrics',col.names = c("metrics", "value")
)

Parallelization takes effect only when size of the elements increases since creating clusters takes time. The mean time of execution is 873.8708 ms, which represent a worsening of approximately 50 porcentual points with respect to the raw implementation

knapsack_dynamic

A less computing intensive approach for the problem would be a dynamic implementation iterating through the dataframe . The algorithm will run in O(W_n).

profiling was carried out in the kanpsack dynamic algorithm. We run the algorithm over 300 and later 500 objects. 
The following table shows some performance metrics and time to carry out the execution over 300-500 objects using dynamic implementation.

Lab06::knapsack_dynamic(x = knapsack_objects[1:500,], W = 3500)

table = cbind(c("mean before profiling (300 objects)", "after profiling (300 objects)", "after profiling (500 objects)" ), c("61.44432 ms", "27.24009 ms", "2.427855 s"))

knitr::kable(
  table, caption = 'Profiling Metrics',col.names = c("metrics", "value")
)

The mean time of execution with is 27.24009 ms, which represents an improvement of approximately 56 porcentual points with respect to the non-profiled one. With the 500 objects execution, the time rises to 2.43 s.

Measured with: microbenchmark.

greedy_knapsack

The last approach will be a heuristic approximation. The algorithm will run in O(nlog(n)) due to the sorting part.

 Lab06::greedy_knapsack(x = knapsack_objects[1:1e+06, ], W = 3500)

Units: milliseconds
The following table shows some performance metrics and time to carry out the execution over 1000000 objects using greedy implementation.

The mean time of execution with 1000000 objects is 1044.997 ms.

table = cbind(c( "min", "lq", "mean", "median", "uq", "max", "neval"), c("824.3755", "989.3942", "1045.773", "1044.997", "1088.741", "1261.094",   "100"))

knitr::kable(
  table, caption = 'Performance Metrics',col.names = c("metrics", "value")
)