decomposeArbFLSSS: arbFLSSS decomposition

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

arbFLSSS decomposition

Description

Decompose an arbFLSSS instance into sub-problems for distributed computing.

Usage

decomposeArbFLSSS(
  len,
  V,
  target,
  approxNinstance = 1000L,
  maxCore = 7L,
  ksumTable = NULL,
  ksumK = 4L,
  ksumTableSizeScaler = 30L,
  verbose = TRUE
  )

Arguments

len	See the same argument in arbFLSSS().
V	See the same argument in arbFLSSS().
target	See the same argument in arbFLSSS().
approxNinstance	See the same argument in arbFLSSS().
maxCore	See the same argument in arbFLSSS(). The decomposition is single-threaded, but building the k-sum accelerator is multithreaded.
ksumTable	Either NULL or the return value from ksumHash(). ksumTable is not necessary for the decomposition. The function merely store a reference to it in every arbFLSSS object.
ksumK	See the same argument in arbFLSSS(). If ksumK >= 3 and ksumTable == NULL, the function will build a k-sum accelerator and store a reference in every arbFLSSS object.
ksumTableSizeScaler	See the same argument in arbFLSSS().
verbose	See the same argument in arbFLSSS().

Details

The rationale follows decomposeMflsss(). The pair decomposeArbFLSSS() and arbFLSSSobjRun() makes up the distributed computing counterpart of arbFLSSS().

Value

A list of two:

$arbFLSSSobjects: a list. Each element is an arbFLSSS object that would be supplied to arbFLSSSobjRun().

$solutionsFound: a list. Solutions found during decomposition.

Examples

set.seed(42)
d = 5L # Set dimension.
N = 60L # Set size.
len = 10L # Subset size.
roundN = 2L # For rounding the numeric values before conversion to strings.


V = matrix(round(runif(N * d, -1e5, 1e5), roundN), nrow = N) # Make superset.
sol = sample(N, len) # Make a solution.
target = round(colSums(V[sol, ]), roundN) # Target subset sum.


optionSave = options()
options(scipen = 999) # Ensure numeric => string conversion does not
# produce strings like 2e-3.
Vstr = matrix(as.character(V), nrow = N) # String version of V.
targetStr = as.character(target)


system.time({
  theDecomposed = FLSSS::decomposeArbFLSSS(
    len = len, V = Vstr, target = targetStr, approxNinstance = 1000,
    maxCore = 2, ksumTable = NULL, ksumK = 4, verbose = TRUE)
})


# Check if any solution has been found during decomposition.
str(theDecomposed$solutionsFound)


# Check the first arbFLSSS object.
str(theDecomposed$arbFLSSSobjects[[1]])


options(optionSave)

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