### 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 language | English (US) |
---|---|

Pages (from-to) | 194-213 |

Number of pages | 20 |

Journal | British Journal of Mathematical and Statistical Psychology |

Volume | 69 |

Issue number | 2 |

DOIs | |

State | Published - May 1 2016 |

### Fingerprint

### 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

*British Journal of Mathematical and Statistical Psychology*,

*69*(2), 194-213. https://doi.org/10.1111/bmsp.12068

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

Research output: Contribution to journal › Article

*British Journal of Mathematical and Statistical Psychology*, vol. 69, no. 2, pp. 194-213. https://doi.org/10.1111/bmsp.12068

}

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 -