The penalty-free heterogeneous p-median problem: formulations and algorithms
Clustering; Optimization; Marketing Science
The Heterogeneous P-Median Problem was recently proposed as an alternative model
to traditional clustering methods. It is appropriated to represent heterogeneity in clustering problems in which a proximity matrix is considered for each individual involved in the sorting task. The original heterogeneous p-median problem is a nonconvex and parametric MINLP problem. In this work, a new model for clustering individuals with distinct proximity matrices is proposed. In particular, it removes from the previous model the need for adjusting a penalty factor in the objective function that balanced the sum of dissimilarities between each object and its assigned category, conditional on
group membership, and a second term that minimized the difference between the number of piles the individual makes in the sorting task and the estimated number of piles, using the number of medians estimated for each group. This penalty had to be adjusted by the expert in a case-by-case basis. Besides eliminating the need for the penalty factor, the model proposed here automatically obtains the number of medians in each group. The problem is exactly solved by a mixed-integer programming solver after it is reformulated with the reformulation-linearization technique. For tackling larger instances, a genetic algorithm is proposed. Finally, a real-world instance is used as a case to demonstrate and validate the application of the new model.