Multilevel iterated tabu search for the multi-constraint graph partitioning problem
针对多约束图划分这一NP难问题，提出了首个多级迭代禁忌搜索算法，在665个基准实例中找到了573个新上界，显著优于现有方法。
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.