Variable Neighborhood Descent applied to Multi-way Number Partitioning Problem

This paper presents an algorithm for the optimization version of the Multi-Way Number Partitioning Problem (MWNPP). This problem consists in distributing the elements of a given sequence into k disjoint subsets so that the sums of each subset elements fit in the shortest interval. The metaheuristic Variable Neighborhood Descent (VND), a deterministic variant of Variable Neighborhood Search (VNS), adapted for solving the MWNPP, has a good performance over instances less than six subsets. It is carried out a comparative study with two algorithms, Karmarkar-Karp Heuristic and Longest Processing Time, using randomly generated instances and objective functions values. The statistical tests show that results of the VND proposed are significantly better than literature constructive methods and its improvements.