IMPart: Integration of Memetic Operations into Multi-Level Framework for Large-k-Way Hypergraph Partitioning
For practitioners in VLSI design and scientific computing needing high-quality large-k hypergraph partitions, IMPart provides a practical memetic approach that is faster than prior memetic methods while achieving superior solution quality.
IMPart integrates memetic operations (recombination and mutation) directly into the uncoarsening phase of a multi-level hypergraph partitioner, achieving higher-quality solutions for large-k-way partitioning and outperforming all existing methods on standard benchmarks.
The problem of k-way hypergraph partitioning is fundamental with significant applications in various fields, including VLSI design and scientific computing. State-of-the-art hypergraph partitioners commonly employ a multi-level framework encompassing coarsening, initial partitioning, uncoarsening, and refinement phases. However, many existing methods do not scale well to problems requiring a large number of partitions (i.e., large k). In pursuit of exceptionally high solution quality, existing memetic approaches often execute their two key operations, recombination and mutation, by invoking separate, standalone multi-level partitioners. This design choice, however, renders them significantly more time-consuming than standard multi-level partitioners. To make such memetic approaches more practical, we propose an advanced memetic framework, IMPart, which introduces novel recombination and mutation operators and integrates them directly into the uncoarsening phase of a single multi-level framework. This transforms the local searches of different granularities in the traditional multi-level framework into a sophisticated, collaborative search. Experimental results on multiple standard benchmarks demonstrate our framework more effectively escapes local optima and explores the global solution space for higher-quality solutions, substantially outperforming all existing hypergraph partitioners for large-$k$-way hypergraph partitioning. Our framework highlights a new paradigm for the development of advanced hypergraph partitioners.