Improved Variable-Relationship Guided LNS for the Data Centre Machine Reassignment Problem

Large Neighborhood Search (LNS) is a potent metaheuristic technique for addressing complex Combinatorial Optimization Problems by focusing in each iteration on smaller, more manageable subproblems. However, a significant challenge in the adoption of LNS has been the need for domain experts to define effective problem-specific neighborhoods. In this paper, we present an improvement to our previously proposed Variable-Relationship Guided LNS, which is a generic LNS approach that builds each neighborhood such that it would be structurally connected (based on the problem constraints). There are two major differences in our new approach. The first is that the method for selecting structurally connected variables incorporates a better discriminator, and the second is that only half the neighborhood is built with this, the remaining half is filled in a much more stochastic manner. We conduct extensive experiments with our approach on the widely studied Machine Reassignment Problem instances proposed by Google. Our results demonstrate that our Improved VR-G LNS outperforms the original in this complex Combinatorial Optimization Problem and achieves results near to the domain-specific heuristics. This helps achieve the goal of making LNS more accessible to a wider range of applications of complex Large-Scale combinatorial optimisation without need of domain experts for neighborhood designing.