mFLSSSpar: Multithreaded multidimensional Subset Sum given error...

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

Multithreaded multidimensional Subset Sum given error thresholds

Description

The multidimensional version of FLSSS(). See decomposeMflsss() for the multi-process version.

Usage

mFLSSSpar(
  maxCore = 7L,
  len,
  mV,
  mTarget,
  mME,
  solutionNeed = 1L,
  tlimit = 60,
  dl = ncol(mV),
  du = ncol(mV),
  useBiSrchInFB = FALSE,
  avgThreadLoad = 8L
  )

Arguments

maxCore	Maximal threads to invoke. Ideally maxCore should not surpass the total logical processors on machine.
len	An integer as the subset size. See len in FLSSS().
mV	A data frame or a matrix as the multidimensional set, columns as dimensions.
mTarget	A numeric vector of size ncol(mV) as the subset sum.
mME	A numeric vector of size ncol(mV) as the subset sum error thresholds.
solutionNeed	See solutionNeed in FLSSS().
tlimit	See tlimit in FLSSS().
dl	An integer no greater than ncol(mV). Let sol be the index vector of a solution. Let dls <- 1L : dl. The following is true: colSums(mV[sol, dls]) >= mTarget[dls] - mME[dls].
du	An integer no greater than ncol(mV). Let sol be the index vector of a solution. Let dus <- (ncol(mV) - du + 1) : ncol(mV). The following is true: colSums(mV[sol, dus]) <= mTarget[dus] + mME[dus].
useBiSrchInFB	See useBiSrchInFB in FLSSS().
avgThreadLoad	If mV is comonotonic, mFLSSSpar() warms up with a breadth-first search and then spawns at least B branches for parallelization. B equals the first power-of-two integer no less than avgThreadLoad * maxCore.

Value

A list of index vectors.

Examples

# rm(list = ls()); gc()
subsetSize = 7L
supersetSize = 60L
dimension = 5L # dimensionality


# Create a supertset at random:
N = supersetSize * dimension
superset = matrix(1000 * (rnorm(N) ^ 3 + 2 * runif(N) ^ 2 +
  3 * rgamma(N, 5, 1) + 4), ncol = dimension)
rm(N)


# Plant a subset sum:
solution = sample(1L : supersetSize, subsetSize)
subsetSum = colSums(superset[solution, ])
subsetSumError = abs(subsetSum) * 0.01 # relative error within 1%
rm(solution)


# Mine subsets, dimensions fully bounded
rst = FLSSS::mFLSSSpar(maxCore = 2, len = subsetSize, mV = superset,
                       mTarget = subsetSum, mME = subsetSumError,
                       solutionNeed = 2, dl = ncol(superset), du = ncol(superset),
                       tlimit = 2, useBiSrchInFB = FALSE, avgThreadLoad = 8L)


# Verify:
cat("Number of solutions = ", length(rst), "\n")
if(length(rst) > 0)
{
  cat("Solutions unique: ")
  cat(length(unique(lapply(rst, function(x) sort(x)))) == length(rst), "\n")
  cat("Solutions correct: ")
  cat(all(unlist(lapply(rst, function(x)
    abs(colSums(superset[x, ]) - subsetSum) <= subsetSumError))), "\n")
} else
{
  cat("No solutions exist or timer ended too soon.\n")
}




# Mine subsets, the first 3 dimensions lower bounded,
# the last 4 dimension upper bounded
rst = FLSSS::mFLSSSpar(maxCore = 2, len = subsetSize, mV = superset,
                       mTarget = subsetSum, mME = subsetSumError,
                       solutionNeed = 2, dl = 3L, du = 4L,
                       tlimit = 2, useBiSrchInFB = FALSE, avgThreadLoad = 8L)


# Verify:
cat("Number of solutions = ", length(rst), "\n")
if(length(rst) > 0)
{
  cat("Solutions unique: ")
  cat(length(unique(lapply(rst, function(x) sort(x)))) == length(rst), "\n")
  cat("Solutions correct: ")
  cat(all(unlist(lapply(rst, function(x)
  {
    lowerBoundedDim = 1L : 3L
    lowerBounded = all(colSums(superset[x, lowerBoundedDim]) >=
      subsetSum[lowerBoundedDim] - subsetSumError[lowerBoundedDim])


    upperBoundedDim = (ncol(superset) - 3L) : ncol(superset)
    upperBounded = all(colSums(superset[x, upperBoundedDim]) <=
      subsetSum[upperBoundedDim] + subsetSumError[upperBoundedDim])


    lowerBounded & upperBounded
  }))), "\n")
} else
{
  cat("No solutions exist or timer ended too soon.\n")
}

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