Effectiveness of the MineReduce approach in reducing the size of combinatorial optimization problem instances

¹ Instituto de Computaçãao, Universidade Federal Fluminense, Niterói 24210-346, RJ, Brazil
² Escola Nacional de Ciências Estatísticas, Instituto Brasileiro de Geografia e Estatística, Rio de Janeiro 20271-020, RJ, Brazil

^* Corresponding author: mmaia@ic.uff.br; marcelo.h.maia@ibge.gov.br

Received: 4 October 2023
Accepted: 23 January 2024

Abstract

Previous work has shown that the performance of metaheuristics can benefit from using data mining techniques, which can improve the obtained solutions. In a strategy that has been successfully used for over a decade, data mining techniques are applied to extract patterns from good solutions found in the early stages of the heuristic process, and these patterns are introduced into the solutions generated afterwards. Recently, a novel approach that uses data mining for problem size reduction, called MineReduce, has been proposed and achieved even more impressive results in improving metaheuristics. In this work, we apply the MineReduce approach to improve the performance of a multi-start iterated tabu search algorithm. The results show that with the incorporation of the MineReduce approach, the method can obtain better solutions while spending less time. Additionally, we assessed the effectiveness of the size reduction performed by MineReduce, comparing it to a kernelization algorithm. Despite the lack of guarantees on optimality or size-bounding, the reduction carried out by MineReduce was effective in practice.