Applying a Fixed Set Search Matheuristic for Partitioning Graphs with Supply and Demand

In recent years, increasing attention has been given to the partitioning of electrical distribution systems. One important area of research concerns interconnected microgrids, where the objective is to balance energy generation and consumption across individual microgrids. Graph-based models provide an effective approach for representing such systems. In particular, interconnected microgrid networks can be formulated as instances of the maximum partitioning of graphs with supply and demand (MPGSD) problem. Applying matheuristics to such optimization problems requires careful consideration of the underlying problem structure, constraints, and characteristics. In this paper, we investigate the application of a fixed set search matheuristic to the MPGSD problem. We exploit the structural properties of the problem to develop a problem-specific configuration of the matheuristic and analyze its performance across different graph classes. Computational results show that the proposed approach achieves superior solution quality on tree graphs while remaining competitive with existing approaches on small- to medium-sized general graph instances. In addition to evaluating solution quality, we provide a detailed analysis of the matheuristic’s runtime behavior and investigate the relationship between the number of fixed variables and the resulting solution quality. The results provide insights into how the degree of variable fixing influences the trade-off between computational effort and solution quality, highlighting the importance of appropriately selecting the search parameters based on the underlying graph structure.