A heuristic search based on diversity for solving combinatorial problems

In this paper we propose a novel heuristic search for solving combinatorial optimization problems which we call Diverse Search (DS). Like beam search, this constructive approach expands only a selected subset of the solutions in each level of the search tree. However, instead of selecting the solutions with the best values, we use an efficient method to select a diverse subset, after filtering out uninteresting solutions. DS also distinguishes solutions that do not produce better offspring, and applies a local search process to them. The intuition is that the combination of these strategies allows to reach more—and more diverse—local optima, increasing the chances of finding the global optima. We test DS on several instances of the Köerkel–Ghosh (KG) and K-median benchmarks for the Simple Plant Location Problem. We compare it with a state-of-the-art heuristic for the KG benchmark and the relatively old POPSTAR solver, which also relies on the idea of maintaining a diverse set of solutions and, surprisingly, reached a comparable performance. With the use of a Path Relinking post-optimization step, DS can achieve results of the same quality that the state-of-the-art in similar CPU times. Furthermore, DS proved to be slightly better on average for large scale problems with small solution sizes, proving to be an efficient algorithm that delivers a set of good and diverse solutions.