decomposeMflsss {FLSSS} | R Documentation |
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 |
mV |
See the same argument in |
mTarget |
See the same argument in |
mME |
See the same argument in |
solutionNeed |
See the same argument in |
dl |
See the same argument in |
du |
See the same argument in |
useBiSrchInFB |
See the same argument in |
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))
}