decomposeMflsss: mFLSSS decomposition

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

mFLSSS decomposition

Description

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

Usage

decomposeMflsss(
  len,
  mV,
  mTarget,
  mME,
  solutionNeed = 1L,
  dl = ncol(mV),
  du = ncol(mV),
  useBiSrchInFB = FALSE,
  approxNinstance = 50000L
  )

Arguments

len	See the same argument in mFLSSSpar().
mV	See the same argument in mFLSSSpar().
mTarget	See the same argument in mFLSSSpar().
mME	See the same argument in mFLSSSpar().
solutionNeed	See the same argument in mFLSSSpar().
dl	See the same argument in mFLSSSpar().
du	See the same argument in mFLSSSpar().
useBiSrchInFB	See the same argument in mFLSSSpar().
approxNinstance	Approximately how many instances should the problem be decomposed into.

Details

This function and mFLSSSobjRun() constitute a multi-process counterpart of mFLSSSpar(). It decomposes a multidimensional subset sum problem into numerous independent instances that can be submitted to any computing resource of CPU threads, on each of which mFLSSSobjRun() receives and solves the instance.

For example, if 1000 threads are available, either on a computing cluster or on a few hundred laptops, one could (i) decompose the problem of interest into 100000 instances using decomposeMflsss(), (ii) transmit each instance to any available thread and calls mFLSSSobjRun() on the instance, (iii) collect the results from all threads. It is strongly recommended to decompose the initial problem into much more instances than the threads, provided that an automatic queueing system exists, so there would be less chance of having idling threads during computation — if the number of instances equals the number of threads, some threads may finish earlier than others due to the heterogeneous nature of the instances, thus the computing waste.

The pair decomposeMflsss() and mFLSSSobjRun() is designed for exploiting distributed resource to solve large and hard multidimensional subset sum instances.

Value

A list of two:

$mflsssObjects: a list. Each element is an mFLSSS object that would be supplied to mFLSSSobjRun().

$solutionsFound: a list. Solutions found during decomposition.

Examples

N = 30L # Superset size.
len = 6L # Subset size.
dimen = 5L # Dimension.
set.seed(8120)
v = matrix(runif(N * dimen) * 1000, nrow = N) # Superset.
sol = sample(N, len)
target = colSums(v[sol, ]) # Target sum.
ME = target * 0.03 # Error threshold.
approxNinstance = 1000


validate = function(len, v, target, ME, result)
{
  all(unlist(lapply(result, function(x)
    all(abs(colSums(v[x, ]) - target) <= ME))))
}


decompedFlsss = FLSSS::decomposeMflsss(
  len = len, mV = v, mTarget = target, mME = ME, solutionNeed = 1e6,
  approxNinstance = approxNinstance)


str(decompedFlsss$solutionsFound) # See if the agent already found
# some solutions and validate them.
if(length(decompedFlsss$solutionsFound) > 0)
  print(validate(len, v, target, ME, decompedFlsss$solutionsFound))


length(decompedFlsss$mflsssObjects) # Number of independent small jobs.
someOtherSolutions = FLSSS::mFLSSSobjRun(
  decompedFlsss$mflsssObjects[[620]], tlimit = 3, solutionNeed = 1e6)


if(length(someOtherSolutions) > 0) # Validate solutions.
{
  print(someOtherSolutions)
  print(validate(len, v, target, ME, someOtherSolutions))
}

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