An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers

We present a mixed integer programming formulation for the problem of clustering a set of points in Rd with axis-parallel clusters, while allowing to discard a pre-specified number of points, thus declared to be outliers. We identify a family of valid inequalities separable in polynomial time, we...

Descripción completa

Detalles Bibliográficos
Autor principal: Marenco, Javier
Formato: info:eu-repo/semantics/preprint submittedVersion
Lenguaje:Inglés
Publicado: Universidad Torcuato Di Tella 2023
Materias:
Clustering
Integer programming
Facets
Cutting planes
Acceso en línea:https://repositorio.utdt.edu/handle/20.500.13098/12149
Aporte de:
Repositorio Digital Universidad Torcuato Di Tella de Universidad Torcuato Di Tella
id I57-R163-20.500.13098-12149
record_format dspace
spelling I57-R163-20.500.13098-121492023-11-23T07:00:26Z An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers Marenco, Javier Clustering Integer programming Facets Cutting planes We present a mixed integer programming formulation for the problem of clustering a set of points in Rd with axis-parallel clusters, while allowing to discard a pre-specified number of points, thus declared to be outliers. We identify a family of valid inequalities separable in polynomial time, we prove that some inequalities from this family induce facets of the associated polytope, and we show that the dynamic addition of cuts coming from this family is effective in practice. 2023-11-22T15:07:04Z 2023-11-22T15:07:04Z 2023 info:eu-repo/semantics/preprint info:eu-repo/semantics/submittedVersion https://repositorio.utdt.edu/handle/20.500.13098/12149 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-sa/2.5/ar/ 23 p. application/pdf application/pdf Universidad Torcuato Di Tella
institution Universidad Torcuato Di Tella
institution_str I-57
repository_str R-163
collection Repositorio Digital Universidad Torcuato Di Tella
language Inglés
orig_language_str_mv eng
topic Clustering
Integer programming
Facets
Cutting planes
spellingShingle Clustering
Integer programming
Facets
Cutting planes
Marenco, Javier
An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
topic_facet Clustering
Integer programming
Facets
Cutting planes
description We present a mixed integer programming formulation for the problem of clustering a set of points in Rd with axis-parallel clusters, while allowing to discard a pre-specified number of points, thus declared to be outliers. We identify a family of valid inequalities separable in polynomial time, we prove that some inequalities from this family induce facets of the associated polytope, and we show that the dynamic addition of cuts coming from this family is effective in practice.
format info:eu-repo/semantics/preprint
submittedVersion
author Marenco, Javier
author_facet Marenco, Javier
author_sort Marenco, Javier
title An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
title_short An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
title_full An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
title_fullStr An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
title_full_unstemmed An integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
title_sort integer programming approach for the hyper-rectangular clustering problem with axis-parallel clusters and outliers
publisher Universidad Torcuato Di Tella
publishDate 2023
url https://repositorio.utdt.edu/handle/20.500.13098/12149
work_keys_str_mv AT marencojavier anintegerprogrammingapproachforthehyperrectangularclusteringproblemwithaxisparallelclustersandoutliers
AT marencojavier integerprogrammingapproachforthehyperrectangularclusteringproblemwithaxisparallelclustersandoutliers
_version_ 1808040621961641984

Ejemplares similares