Mohammed Najib Haouas, Daniel Aloise and Gilles Pesant
Conference or Workshop Item - Paper (2020)
|
Accepted Version Terms of Use: All rights reserved. Download (976kB) |
Cite this document: | 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 presented at 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2020), Vienna, Austria. doi:10.1007/978-3-030-58942-4_17 |
---|
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 Technologie de l'information > 2706 Génie logiciel 2700 Technologie de l'information > 2713 Algorithmes 2700 Technologie de l'information > 2714 Mathématiques de l'informatique |
---|---|
Department: | Département de génie informatique et génie logiciel |
Research Center: | Non applicable |
Funders: | CRSNG/NSERC |
Date Deposited: | 21 Sep 2021 16:08 |
Last Modified: | 22 Oct 2021 16:46 |
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 |
Official URL: | 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