Fixed Set Search Applied to the Max-Cut Problem

Abstract

The Max-Cut Problem (MCP) is a classical NP-hard combinatorial optimization problem for graph partitioning, which has many applications such as optimizing electrical grids, or wireless sensor networks. In the context of this paper, the fixed set search (FSS) which is novel metaheuristic that uses a population-based approach is applied for solving the MCP. Initially, the greedy randomized adaptive search procedure (GRASP) is formulated to address the given problem. Subsequently, the FSS incorporates a learning procedure into the GRASP by identifying common elements within high-quality solutions. The primary benefit of this metaheuristic is the simplicity of implementation. The algorithms are tested on standard benchmark instances. The conducted computational experiments validate that the learning procedure of the FSS enhances the effectiveness of the base GRASP method, and outperforms other population based metaheuristics that include local search procedures like the AntCut and the hierarchical social metaheuristics.