auxKnapsack01dp: Multithreaded binary knapsack problem solver via dynamic...

In FLSSS: Mining Rigs for Problems in the Subset Sum Family

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
)

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.

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.

Note

The function is not to solve the 0-1 multiple knapsack problem. weight and caps are integers. Be cautioned that dynamic programming is not suitable for problems with weights or capacities of high magnitudes due to its space complexity. Otherwise it could outperform branch-and-bound especially for large instances with highly correlated item weights and values.

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.  
}

FLSSS documentation built on May 17, 2022, 5:09 p.m.