FLSSS (version 9.2.8)

auxKnapsack01dp: Multithreaded binary knapsack problem solver via dynamic programming

Description

Given items' weights and values, concurrently solve 0-1 knapsack problems to optimality via dynamic programming for multiple knapsacks of different capacities.

Usage

auxKnapsack01dp(
  weight,
  value,
  caps,
  maxCore = 7L,
  tlimit = 60,
  simplify = TRUE
)

Value

A list of 3:

maxValue: a numeric vector. maxValue[i] equals the sum of values of items selected for capacity caps[i].

selection: a list of integer vectors. selection[i] indexes the items selected for capacity caps[i].

lookupTable: a numeric matrix.

Arguments

weight

An integer vector.

value

A numeric vector. The size equals that of weight.

caps

An integer vector of knapsack capacities.

maxCore

Maximal threads to invoke. No greater than the number of logical CPUs on machine.

tlimit

Return the best exsisting solution in tlimit seconds.

simplify

If length(caps) == 1, simplify the output.

Details

Implementation highlights include (i) lookup matrix is only of space complexity O(N * [max(C) - min(W)]), where N = the number of items, max(C) = maximal knapsack capacity, min(W) = minimum item weight; (ii) threads read and write the same lookup matrix and thus accelerate each other; (iii) the return of existing best solutions in time.

Examples

# Examples with CPU (user + system) or elapsed time > 5s
#                 user system elapsed
# auxKnapsack01dp 6.53      0    3.33
# CRAN complains about computing time. Wrap it.
if (FALSE)
{
  set.seed(42)
  weight = sample(10L : 100L, 600L, replace = TRUE) # Dynamic programming
  # solution requires integer
  # weights.
  value = weight ^ 0.5 * 100 # Higher correlation between item weights and values
  # typically implies a harder knapsack problem.
  caps = as.integer(runif(10, min(weight), 600L))
  system.time({rstDp = FLSSS::auxKnapsack01dp(
    weight, value, caps, maxCore = 2, tlimit = 4)})
  system.time({rstBb = FLSSS::auxKnapsack01bb(
    weight, value, caps, maxCore = 2, tlimit = 4)})
  # Dynamic programming can be faster than branch-and-bound for integer weights
  # and capacity of small magnitudes.  
}