General swap-based multiple neighborhood tabu search for the maximum independent set problem

•The Maximum Independent Set problem (MIS) is a well known NP-hard problem.•We present a general Swap-Based Local Search (SBLS) procedure for solving MIS.•SBLS uses a unified (k,1)-swap operator to explore multiple neighborhoods.•SBLS is assessed on three benchmark sets (DIMACS, BHOSLIB, CODE with 131 instances).•Results are compared with seven state of the art algorithms.

Given a graph G=(V,E)G=(V,E), the Maximum Independent Set problem (MIS) aims to determine a subset S⊆VS⊆V of maximum cardinality such that no two vertices of S are adjacent. This paper presents a general Swap-Based Tabu Search (SBTS) for solving the MIS. SBTS integrates distinguished features including a general and unified (k,1)-swap operator, four constrained neighborhoods and specific rules for neighborhood exploration. Extensive evaluations on two popular benchmarks (DIMACS and BHOSLIB) of 120 instances show that SBTS attains the best-known results for all the instances. To our knowledge, such a performance was not reported in the literature for a single heuristic. The best-known results on 11 additional instances from code theory are also attained.