Solving Balanced Multi-Weighted Attribute Set Partitioning Problem with Variable Neighborhood Search

Abstract

This paper considers the Balanced Multi-Weighted Attribute Set Partitioning (BMWASP) problem
which requires finding a partition of a given set of objects with multiple weighted attributes into a
certain number of groups so that each attribute is evenly distributed amongst the groups. Our approach is
to define an appropriate criterion allowing to compare the degree of deviation from the ”perfect balance” for
dierent partitions and then produce the partition that minimizes this criterion. We have proposed a mathematical
model for the BMWASP and its mixed-integer linear reformulation. We evaluated its eciency
through a set of computational experiments. To solve instances of larger problem dimensions, we have
developed a heuristic method based on a Variable Neighborhood Search (VNS). A local search procedure
with ecient fast swap-based local search is implemented in the proposed VNS-based approach. Presented
computational results show that the proposed VNS is computationally ecient and quickly reaches
all optimal solutions for smaller dimension instances obtained by exact solver and provide high-quality
solutions on large-scale problem instances in short CPU times.