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

Fingerprint

Exact Method
Cardinality
Subset
Evaluation
Food
Subset Selection
Sequential Methods
Integer Program
Branch and Bound Algorithm
Branch-and-bound
Linear Program
Rendering
Partitioning
Optimal Solution
Binary
Series
Alternatives
Requirements
Computational

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)

Cite this

An evaluation of exact methods for the multiple subset maximum cardinality selection problem. / Brusco, Michael J.; Köhn, Hans Friedrich; Steinley, Douglas.

In: British Journal of Mathematical and Statistical Psychology, Vol. 69, No. 2, 01.05.2016, p. 194-213.

Research output: Contribution to journalArticle

@article{c01ea17f769743db9646be7c3499fc82,
title = "An evaluation of exact methods for the multiple subset maximum cardinality selection problem",
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.",
keywords = "Branch-and-bound, Exploratory Mokken scale analysis, Integer programming, Item selection, Similarity data",
author = "Brusco, {Michael J.} and K{\"o}hn, {Hans Friedrich} and Douglas Steinley",
year = "2016",
month = "5",
day = "1",
doi = "10.1111/bmsp.12068",
language = "English (US)",
volume = "69",
pages = "194--213",
journal = "British Journal of Mathematical and Statistical Psychology",
issn = "0007-1102",
publisher = "Wiley-Blackwell",
number = "2",

}

TY - JOUR

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

AU - Brusco, Michael J.

AU - Köhn, Hans Friedrich

AU - Steinley, Douglas

PY - 2016/5/1

Y1 - 2016/5/1

N2 - 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.

AB - 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.

KW - Branch-and-bound

KW - Exploratory Mokken scale analysis

KW - Integer programming

KW - Item selection

KW - Similarity data

UR - http://www.scopus.com/inward/record.url?scp=84962650670&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84962650670&partnerID=8YFLogxK

U2 - 10.1111/bmsp.12068

DO - 10.1111/bmsp.12068

M3 - Article

C2 - 27027582

AN - SCOPUS:84962650670

VL - 69

SP - 194

EP - 213

JO - British Journal of Mathematical and Statistical Psychology

JF - British Journal of Mathematical and Statistical Psychology

SN - 0007-1102

IS - 2

ER -