auxKnapsack01bb: Multithreaded binary knapsack problem solver via branch and...

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

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
)

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.

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

Note

The function is not to solve the 0-1 multiple knapsack problem. The C++ implementation is fully independent and borrows no code from any open or commercial source.

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)

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