Premium
An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem †
Author(s) -
Haraguchi Kazuya,
Hashimoto Hideki,
Itoyanagi Junji,
Yagiura Mutsunori
Publication year - 2019
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12619
Subject(s) - iterated function , local search (optimization) , iterated local search , vertex (graph theory) , mathematics , algorithm , set (abstract data type) , independent set , search algorithm , graph , computer science , mathematical optimization , combinatorics , mathematical analysis , programming language
Given an undirected graph G = ( V , E ) and a weight for each vertex, the maximum weighted independent set problem (MWISP) calls for a maximum weight subset I of V such that no two vertices in I are adjacent. In this paper, we present an algorithm based on an iterated local search for the MWISP. We incorporate a branch‐and‐bound method in our local search, which enables the algorithm to search a very large neighborhood. Moreover, we propose a search method that reduces the number of candidate solutions to be searched in the neighborhood without missing improved solutions. The proposed algorithm also features an adaptive memory strategy in which each vertex is associated with a penalty that is used to explore diverse solutions in the iterated local search. We tested our algorithm on several instances taken from the DIMACS website and their weighted counterparts, which included large instances with more than 3000 vertices. From the results, we observed that our algorithm was competitive with existing algorithms for unweighted instances, and it found better solutions for some weighted instances.