Solving the multidimensional maximum bisection problem by a genetic algorithm and variable neighborhood search

Abstract

In this paper, we consider the application of the two metaheuristic approaches: a Genetic Algorithm (GA) and a Variable Neighborhood Search (VNS), on an NP-hard optimization problem: Multi-dimensional Maximum Bisection Problem (MDMBP). MDMBP is a generalization of the Maximum Bisection Problem (MBP), where each graph edge instead of having a singular weight, has a vector of weights. The GA is constructed on a modified integer encoding of individuals, where only the feasible solutions are generated, which allows the application of standard genetic operators. A suitable system of neighborhoods based on changing the component for an increasing number of vertices is implemented in the proposed VNS. Both GA and VNS use two types of local search procedures, both based on swapping the components of pairs of vertices. Our computational results were obtained on MDMBP instances in the literature with up to 1000 vertices and 350000 edges, and the well-known MBP G-set instances with up to 20000 vertices and 41459 edges. The obtained results are statistically analysed and compared with the results of the existing methods for solving MDMBP and MBP.