Model-based automatic neighborhood design by unsupervised learning

The definition of a suitable neighborhood structure on the solution space is a key step when designing a heuristic for Mixed Integer Programming (MIP). In this paper, we move on from a MIP compact formulation and show how to take advantage of its features to automatically design efficient neighborhoods, without any human analysis. In particular, we use unsupervised learning to automatically identify “good” regions of the search space “around” a given feasible solution. Computational results on compact formulations of three well-known combinatorial optimization problems show that, on large instances, the neighborhoods constructed by our procedure outperform state-of-the-art domain-independent neighborhoods.