FLSSS (version 9.2.8)

auxKnapsack01bb: Multithreaded binary knapsack problem solver via branch and bound

Description

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

Usage

auxKnapsack01bb(
  weight,
  value,
  caps,
  itemNcaps = integer(0),
  maxCore = 7L,
  tlimit = 60,
  ub = "MT",
  simplify = TRUE
)

Value

A list of 2:

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

Arguments

weight

A numeric vector.

value

A numeric vector. The size equals that of weight.

caps

A numeric vector of knapsack capacities.

itemNcaps

An integer vector of upper bounds on the number of selected items. itemNcaps[i] corresponds to instance caps[i]. Empty itemNcaps implies no size restriction.

maxCore

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

tlimit

Return the best exsisting solution in tlimit seconds.

ub

Upper bound function.

simplify

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

Details

The algorithm takes the Horowitz-Sahni (1974) and the Martello-Toth (1977) upper bound functions and is carefully engineered towards speed. Implementation highlights include (i) an extra option of upper bounding the number of selected items, which only adds trivial overhead; (ii) the return of existing best solutions in time; (iii) the capability of taking numeric weights and values.

Examples

set.seed(42)
weight = runif(100, min = 1e3, max = 1e6)
value = weight ^ 0.5 * 100 # Higher correlation between item weights and values
                           # typically implies a harder knapsack problem.
caps = runif(10, min(weight), sum(weight))
rst = FLSSS::auxKnapsack01bb(weight, value, caps, maxCore = 2, tlimit = 2)
str(rst)