A reactive self-tuning scheme for multilevel graph partitioning

We propose a new multilevel graph bi-partitioning approach (M-RRTS) using greedy construction and reactive-randomized tabu search (RRTS). RRTS builds upon local search by adding prohibitions (to enforce diversification) and self-tuning mechanisms to adapt meta-parameters in an online manner to the instance being solved. The novel M-RRTS approach adds a multi-scale structure to the previous method. The original graph is summarized through a hierarchy of coarser graphs. At each step, more densely-interconnected nodes at a given level of the hierarchy are coalesced together. The coarsest graph is then partitioned, and uncoarsening phases followed by refinement steps build solutions at finer levels until the original graph is partitioned. A variation of RRTS is applied for the refinement of partitions after each uncoarsening phase. We investigate various building blocks of the proposed multilevel scheme, such as different initial greedy constructions, different tie-breaking options and var...