pipette
ENEnglish

A Benders decomposition approach for hierarchical k-medoids

Rick S. H. Willemsen

Preprint

En palabras de los autores

We study a hierarchical clustering problem formulated as a sum of k-medoids objectives. This problem is related to the multi-period p-median problem, but instead of having nested facilities, we consider a hierarchy of nested assignments. We present two Benders formulations from the p-median literature and show how the obtained nested p-median solutions can be converted into hierarchical k-medoids solutions. We validate our methods on various instances. First, we show on small-scale instances that a standard Benders decomposition approach achieves speedups of up to three orders of magnitude over an existing branch-and-price method, while producing hierarchical k-medoids solutions that are at most 5% away from optimality. Second, we present an aggregated Benders heuristic that can handle instances with more than 13,000 observations.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.