MineReduce-based heuristic for the maximum diversity problem

What the paper says

The Maximum Diversity Problem (MDP) is a challenging NP-hard optimization problem with applications in various domains, including social network analysis, bioinformatics, and facility location. Traditional heuristics often struggle to find high-quality solutions for large-scale MDP instances within reasonable time limits. Recent hybrid heuristics have incorporated data mining techniques to guide the search process, yielding improved solution quality. MineReduce is a successful example of such recent proposals. Its approach leverages mined patterns to contract portions of the problem space, facilitating a more focused and efficient search. In this work, we propose a new heuristic that integrates the MineReduce technique with the MDM_KLD, a previously proposed hybrid heuristic, to solve the MDP. Our approach aims to alleviate the computational burden by periodically solving a reduced version of the problem without compromising the quality of the solutions obtained for the original problem. Computational experiments conducted on three different sets of instances demonstrate the effectiveness of our approach compared to MDM_KLD, achieving superior solution quality in most instances within the same computational time. • A novel heuristic, MR_KLD, combines MineReduce with the MDM_KLD heuristic to solve the Maximum Diversity Problem (MDP). • MineReduce enhances computational efficiency by reducing problem size without compromising solution quality. • The heuristic is benchmarked on the MDG datasets, outperforming existing methods in both solution quality and efficiency. • MR_KLD achieves superior results, showing significant improvements over MDM_KLD in most instances. • The integration of problem size reduction and data mining offers promising avenues for solving other NP-hard optimization problems.