FLSSS

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

Specialized solvers for combinatorial optimization problems in the Subset Sum family. These solvers differ from the mainstream in the options of (i) restricting subset size, (ii) bounding 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 decomposes the problem in a novel approach, and the multi-threaded framework offers exact algorithms 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 user-controlled precision loss, and those integers are further zipped non-uniformly in 64-bit buffers. Arithmetic on compressed integers is done by bit-manipulation and the design has virtually zero speed lag relative to normal integers arithmetic. The consequent reduction in dimensionality may yield substantial acceleration. Compilation with g++ '-Ofast' is recommended. See package vignette (<arXiv:1612.04484v3>) for details. Functions prefixed with 'aux' (auxiliary) are or will be implementations of existing foundational or cutting-edge algorithms for solving optimization problems of interest.

Total

21,341

Last month

513

Last week

114

Average per day

17

Daily downloads

Total downloads

Description file content

Package
FLSSS
Type
Package
Title
Mining Rigs for Specialized Subset Sum, Multi-Subset Sum, Multidimensional Subset Sum, Multidimensional Knapsack, Generalized Assignment Problems
Version
8.5.5
Author
Charlie Wusuo Liu
Maintainer
Charlie Wusuo Liu
Description
Specialized solvers for combinatorial optimization problems in the Subset Sum family. These solvers differ from the mainstream in the options of (i) restricting subset size, (ii) bounding 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 decomposes the problem in a novel approach, and the multi-threaded framework offers exact algorithms 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 user-controlled precision loss, and those integers are further zipped non-uniformly in 64-bit buffers. Arithmetic on compressed integers is done by bit-manipulation and the design has virtually zero speed lag relative to normal integers arithmetic. The consequent reduction in dimensionality may yield substantial acceleration. Compilation with g++ '-Ofast' is recommended. See package vignette () for details. Functions prefixed with 'aux' (auxiliary) are or will be implementations of existing foundational or cutting-edge algorithms for solving optimization problems of interest.
License
GPL-3
Encoding
UTF-8
LazyData
true
ByteCompile
true
Imports
Rcpp (>= 0.12.13), RcppParallel
LinkingTo
Rcpp, RcppParallel
SystemRequirements
GNU make
NeedsCompilation
yes
Packaged
2019-07-09 17:41:58 UTC; i56087
Repository
CRAN
Date/Publication
2019-07-10 08:20:04 UTC

install.packages('FLSSS')

8.5.5

8 days ago

Charlie Wusuo Liu

GPL-3

Imports

Rcpp (>= 0.12.13), RcppParallel

Discussions