Learn R Programming

⚠️There's a newer version (9.2.8) of this package.Take me there.

FLSSS (version 7.6)

Mining Rigs for Specialized Subset Sum, Multi-Subset Sum, Multidimensional Subset Sum, Multidimensional Knapsack, Generalized Assignment Problems

Description

Specialized solvers for combinatorial optimization problems in the Subset Sum family. These solvers differ from the mainstream in the options of (i) subset size restriction, (ii) bounds on the subset elements, (iii) mining real-value sets with predefined subset sum errors, and (iv) finding one or more subsets in limited time. A novel algorithm for mining the one-dimensional Subset Sum induced algorithms for the multi-Subset Sum and the multidimensional Subset Sum. The latter is creatively scheduled in a multi-threaded environment, and the framework offers strong applications to the multidimensional Knapsack and the Generalized Assignment problems. Package updates include (a) renewed implementation of the multi-Subset Sum, multidimensional Knapsack and Generalized Assignment solvers; (b) availability of bounding solution space in the multidimensional Subset Sum; (c) fundamental data structure and architectural changes for enhanced cache locality and better chance of SIMD vectorization; (d) an option of mapping real-domain problems to the integer domain with controlled precision loss, and those integers are further zipped non-uniformly in 64-bit buffers. Arithmetic on compressed integers has a novel design with virtually zero speed lag relative to that on normal integers, and the consequent reduction in dimensionality often leads to substantial acceleration. Compilation with aggressive optimization, e.g. g++ '-Ofast', may speed up mining on some platforms. Package documentation () is outdated as the time of writing.

Copy Link

Version

Install

install.packages('FLSSS')

Monthly Downloads

318

Version

7.6

License

GPL-3

Maintainer

Charlie Wusuo Liu

Last Published

August 28th, 2018

Functions in FLSSS (7.6)

GAP

Generalized Assignment Problem solver
GAPintegerized

An advanced version of GAP().
mFLSSSpar

Multithreaded multidimensional Subset Sum given error thresholds
mFLSSSparImposeBounds

Multithreaded multidimensional Subset Sum in bounded solution space given error thresholds
FLSSS

One-dimensional Subset Sum given error threshold
FLSSSmultiset

Multi-Subset Sum given error threshold
mFLSSSparImposeBoundsIntegerized

An advanced version of mFLSSSparImposeBounds()
mmKnapsack

Multithreaded multidimensional Knapsack problem solver
mmKnapsackIntegerized

An advanced version of mmKnapsack()
mFLSSSparIntegerized

An advanced version of mFLSSSpar()