Multilevel iterated tabu search for the multi-constraint graph partitioning problem

The multi-constraint graph partitioning (MCGP) problem involves partitioning a set of vertices into nonempty, pairwise-disjoint subsets such that each subset must satisfy certain bound constraints while minimizing the total cost of edges with both endpoints in the same subset. Arising from an integrated vehicle and pollster problem in a real-world application, MCGP generalizes a number of other well-known graph partitioning problems. Due to its NP-hard nature, solving MCGP is computationally challenging. This work presents the first multilevel iterated tabu search (MITS) algorithm to tackle MCGP. Specifically, the algorithm uses a problem-specific coarsening method to reduce progressively the input graph and relies on a dedicated feasible-and-infeasible iterated tabu search procedure to refine the solution to each reduced graph. Extensive experiments on two sets of 665 benchmark instances demonstrate that MITS significantly outperforms state-of-the-art algorithms by finding 573 new upper bounds, while matching 83 previous best-known upper bounds. We also apply the algorithm to another related graph partitioning problem to demonstrate its broader applicability. Additionally, we conduct analysis studies on key algorithmic components to verify the effectiveness of the proposed ideas and strategies. • We study the NP-hard multi-constraint graph partitioning problem. • We present the first multilevel optimization-based algorithm to solve the problem. • We present new upper bounds for 573 instances out of 665 benchmark instances. • We show additional results on the balanced k-way partitioning problem with weight constraints. • We analyze the key algorithmic components to evaluate their roles.