Self-adaptive CMSA for solving the multidimensional multi-way number partitioning problem

Abstract

The multidimensional multi-way number partitioning problem takes as input a set of n vectors with a fixed dimension m≥2, and aims to find a partitioning of this set into k≥2 non-empty subsets, such that the sums per coordinate across all subsets are as similar as possible. The problem has applications in key encryption, multiprocessor scheduling, minimization of circuit size and delay, and clustering. This paper employs a hybrid meta-heuristic, a self-adaptive version of the Construct, Merge, Solve, and Adapt algorithm equipped with an efficient local search procedure. Local search was able to accelerate the convergence towards promising regions of the search space. A comprehensive experimental evaluation shows that the proposed algorithm improves over all four competing algorithms from the related literature, especially when it comes to instances with higher k-values, i.e. k≥3. The observed average relative differences are for several instance groups larger than 25% in favor of the proposed algorithm compared to the second-best approach. In fact, a statistical evaluation indicates that our algorithm performs significantly better than the other approaches on all instances with k≥3.