Back to Search
Start Over
An evaluation of exact methods for the multiple subset maximum cardinality selection problem.
- Source :
-
British Journal of Mathematical & Statistical Psychology . May2016, Vol. 69 Issue 2, p194-213. 20p. - Publication Year :
- 2016
-
Abstract
- The maximum cardinality subset selection problem requires finding the largest possible subset from a set of objects, such that one or more conditions are satisfied. An important extension of this problem is to extract multiple subsets, where the addition of one more object to a larger subset would always be preferred to increases in the size of one or more smaller subsets. We refer to this as the multiple subset maximum cardinality selection problem ( MSMCSP). A recently published branch-and-bound algorithm solves the MSMCSP as a partitioning problem. Unfortunately, the computational requirement associated with the algorithm is often enormous, thus rendering the method infeasible from a practical standpoint. In this paper, we present an alternative approach that successively solves a series of binary integer linear programs to obtain a globally optimal solution to the MSMCSP. Computational comparisons of the methods using published similarity data for 45 food items reveal that the proposed sequential method is computationally far more efficient than the branch-and-bound approach. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00071102
- Volume :
- 69
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- British Journal of Mathematical & Statistical Psychology
- Publication Type :
- Academic Journal
- Accession number :
- 114436807
- Full Text :
- https://doi.org/10.1111/bmsp.12068