<  Back to the Polytechnique Montréal portal

An exact CP approach for the cardinality-constrained euclidean minimum sum-of-squares clustering problem

Mohammed Najib Haouas, Daniel Aloise and Gilles Pesant

Conference or Workshop Item - Paper (2020)

[img]
Preview
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
Show abstract Hide abstract

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.

Open Access document in PolyPublie
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/
Document issued by the official publisher
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

Repository Staff Only