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.