An evaluation of exact methods for the multiple subset maximum cardinality selection problem

Michael J. Brusco, Hans Friedrich Köhn, Douglas Steinley

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)194-213
Number of pages20
JournalBritish Journal of Mathematical and Statistical Psychology
Volume69
Issue number2
DOIs
StatePublished - May 1 2016

Keywords

  • Branch-and-bound
  • Exploratory Mokken scale analysis
  • Integer programming
  • Item selection
  • Similarity data

ASJC Scopus subject areas

  • Statistics and Probability
  • Arts and Humanities (miscellaneous)
  • Psychology(all)

Fingerprint Dive into the research topics of 'An evaluation of exact methods for the multiple subset maximum cardinality selection problem'. Together they form a unique fingerprint.

  • Cite this