A Co-occurrence Graph-Based Approach to the Explainability of Solutions to the P-Median Problem

Metaheuristics are widely used to solve complex combinatorial problems, but the solutions produced often remain non-transparent to the decision-maker. This work proposes an explainability approach to meta-heuristics based on the analysis of co-occurrence relationships between recurrent components of high-quality solutions. These relationships are represented by graphs, from which structures such as communities, max-k-cut, k-cores, and densest subgraphs are extracted in order to identify regularities in the solution space explored by the algorithm. The p-median problem is adopted as an experimental environment, due to its relevance in the literature and the availability of classical benchmark instances. The results indicate that the approach reveals recurrent structural patterns associated with the best solutions with low computational cost, evidencing its potential as an explainability mechanism for meta-heuristics.