EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

995. Variable aggregation in a Benders decomposition for the p-median problem

Invited abstract in session MA-61: Advances in Location Analysis , stream Locational Analysis.

Monday, 8:30-10:00
Room: S10 (building: 101)

Authors (first author is the speaker)

1. Rick Willemsen
Econometric Institute, Erasmus University Rotterdam
2. Daniel Aloise
Polytechnique Montreal
3. Raf Jans
Department of Logistics and Operations Management , HEC Montreal

Abstract

The p-median problem is a classical discrete location problem and is equivalent to the well-known k-medoids problem in the unsupervised clustering literature. The aim is to select p centers while minimizing the sum of distances from each customer to its nearest center. Recent advancements in solving the p-median and related problems have successfully leveraged Benders decomposition methods. In order to reduce the number of variables and possibly the number of Benders cuts in these models, it is possible to aggregate distance variables corresponding to customers. We propose to partially aggregate the distance variables based on an initial solution: aggregation occurs only when the corresponding customers are assigned to the same center in the initial solution. In addition, we propose a set of tailored valid inequalities for these aggregated variables. Initial experiments indicate that our model, post-initialization, provides a stronger lower bound, thereby accelerating the resolution of the root node. Furthermore, this approach seems to positively impact the branching procedure, leading to an overall faster Benders decomposition method.

Keywords

Status: accepted

Back to the list of papers