<  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

Paper (2020)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Accepted Version
Terms of Use: All rights reserved
Download (340kB)
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.

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

Repository Staff Only

View Item View Item