Large Scale Constrained Clustering With Reinforcement Learning
Benedikt Schesch Marco Caserta
Given a network, allocating resources at clusters level, rather than at each
node, enhances efficiency in resource allocation and usage. In this paper, we
study the problem of finding fully connected disjoint clusters to minimize the
intra-cluster distances and maximize the number of nodes assigned to the
clusters, while also ensuring that no two nodes within a cluster exceed a
threshold distance. While the problem can easily be formulated using a binary
linear model, traditional combinatorial optimization solvers struggle when
dealing with large-scale instances. We propose an approach to solve this
constrained clustering problem via reinforcement learning. Our method involves
training an agent to generate both feasible and (near) optimal solutions. The
agent learns problem-specific heuristics, tailored to the instances encountered
in this task. In the results section, we show that our algorithm finds near
optimal solutions, even for large scale instances.