EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2498. Improving pricing strategies on a branch-and-price algorithm for the hyper-rectangular clustering problem with axis-parallel clusters

Invited abstract in session TC-27: Mathematical Optimization for Trustworthy Machine Learning, stream Mathematical Optimization for XAI.

Tuesday, 12:30-14:00
Room: 047 (building: 208)

Authors (first author is the speaker)

1. Diego Delle Donne
IDS department, ESSEC Bussines School
2. Javier Marenco
Business School, Universidad Torcuato Di Tella
3. Eduardo Moreno
Faculty of Engineering and Sciences, Universidad Adolfo Ibañez

Abstract

Given a set of points in the space of an arbitrary dimension, the hyper-rectangular clustering problem with axis-parallel clusters (HRC-AP) consists in grouping the points into clusters, each cluster being determined by a hyper-rectangle in the corresponding space. HRC-AP has been proposed as a model for explainable clustering, as it is straightforward to describe the clusters by the bounds defining each hyper-rectangle: if each coordinate corresponds to a relevant parameter in the application generating the points, then a cluster is specified by its bounds on each parameter.
A variant of HRC-AP considering the existence of outliers (called HRC-APO), allows a certain number of points to be discarded and not included in any cluster. In previous works, we explored integer programming techniques for HRC-APO proposing several formulations and algorithms. We showed that extended formulations (solved via branch-and-price) outperformed classical compact formulations. Nevertheless, these techniques fall short as soon as the number of points to be clustered is increased to medium-sized real-life instances.
In this work we propose an innovative strategy to solve the pricing problem by modeling it as a flow problem. This allows us to develop a polynomial-time routine for the pricing, qualitatively improving the performance of previous approaches. We compare the efficiency of the new method against the existing ones by providing an exhaustive computational experimentation.

Keywords

Status: accepted

Back to the list of papers