A Benders decomposition approach for hierarchical k-medoids
Abstract
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.
Related
- Accelerated Benders decomposition for bi-objective mixed integer programming
- A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons
- Venusian Radio Occultation Constellation Design and Reconfiguration Problems: A Benders Decomposition Approach
- A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows
- An Efficient Randomized Hierarchical Tucker Decomposition
BibTeX
@misc{willemsen2026benders,
title = {{A Benders decomposition approach for hierarchical k-medoids}},
author = {Rick S. H. Willemsen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25757},
eprint = {2610.25757},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25757},
}
RIS
TY - UNPB
TI - A Benders decomposition approach for hierarchical k-medoids
AU - Rick S. H. Willemsen
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25757
UR - https://arxiv.org/abs/2610.25757
AB - 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.
ER -