Seminar – Variable aggregation in a Benders decomposition for the p-median problem

 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.

Room ET-14