Abstract:

Cluster analysis in machine learning aims to partition data points into several groups, while location problems in operations research focus on selecting facilities to serve locations. These problems are closely related and can be addressed using similar methodologies. We examine two such problems: hierarchical clustering and the p-median problem. In hierarchical clustering a hierarchy of nested data partitions needs to be obtained. Although several objective functions have been proposed, exact methods that find optimal solutions based on global objective functions have received little attention. We introduce several exact mathematical programming approaches that optimize an objective function involving a sum of partitional clustering objectives over each level. In the p-median problem the goal is to select p facilities while minimizing the sum of distances from each location to its nearest facility. Recent advancements have successfully leveraged decomposition methods. The current bottleneck is the large number of variables and cuts that are needed. We consider variable aggregation to reduce the size of these models. Numerical experiments are presented for both problems, demonstrating the effectiveness of the proposed approaches.

General information:

This seminar will be organised in a hybrid setup. If you are interested in joining this seminar, please send an email to the secretariat of Amsterdam Business School at secbs-abs@uva.nl.