Mohammed Najib Haouas, Daniel Aloise and Gilles Pesant
Paper (2020)
|
Open Access to the full text of this document Accepted Version Terms of Use: All rights reserved Download (340kB) |
Abstract
Clustering consists in finding hidden groups from unlabeled data which are as homogeneous and well-separated as possible. Some contexts impose constraints on the clustering solutions such as restrictions on the size of each cluster, known as cardinality-constrained clustering. In this work we present an exact approach to solve the Cardinality-Constrained Euclidean Minimum Sum-of-Squares Clustering Problem. We take advantage of the structure of the problem to improve several aspects of previous constraint programming approaches: lower bounds, domain filtering, and branching. Computational experiments on benchmark instances taken from the literature confirm that our approach improves our solving capability over previously-proposed exact methods for this problem.
Subjects: |
2700 Information technology > 2706 Software engineering 2700 Information technology > 2713 Algorithms 2700 Information technology > 2714 Mathematics of computing |
---|---|
Department: | Department of Computer Engineering and Software Engineering |
Funders: | CRSNG/NSERC |
PolyPublie URL: | https://publications.polymtl.ca/9185/ |
Conference Title: | 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2020) |
Conference Location: | Vienna, Austria |
Conference Date(s): | 2020-09-21 - 2020-09-24 |
Publisher: | Springer |
DOI: | 10.1007/978-3-030-58942-4_17 |
Official URL: | https://doi.org/10.1007/978-3-030-58942-4_17 |
Date Deposited: | 21 Sep 2021 16:08 |
Last Modified: | 27 Sep 2024 12:23 |
Cite in APA 7: | Haouas, M. N., Aloise, D., & Pesant, G. (2020, September). An exact CP approach for the cardinality-constrained euclidean minimum sum-of-squares clustering problem [Paper]. 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2020), Vienna, Austria. https://doi.org/10.1007/978-3-030-58942-4_17 |
---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions