INSTANCE ANALYSIS OF THE MAXIMUM DIVERSITY PROBLEM WITH SUPERVISED LEARNING

This work investigates the application of supervised machine learning techniques in the approximate resolution of the maximum diversity problem. Models such as Logistic Regression, k-Nearest Neighbors, decision trees, random forest and neural networks were explored, trained from 315 instances of MDPLib. The instances were pre-processed with extraction of structural characteristics from the graphs and class balancing, in addition to the PCA technique for dimensionality reduction. The models were evaluated based on the proximity of the obtained solutions in relation to the optimal values provided by an exact method and solutions of a meta-heuristic. The results show that, even with moderate accuracy, the models reached up to 95.66% of the maximum diversity in instances with up to 3000 vertices, evidencing the feasibility and scalability of the approach. This study paves the way for the use of supervised learning in large-scale combinatorial problems, reinforcing its potential as a complementary tool to traditional heuristic approaches.