An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†

• Date: 01 July 2019
• Author: Hideki Hashimoto,Mutsunori Yagiura,Kazuya Haraguchi,Junji Itoyanagi
• Published date: 01 July 2019
• DOI: http://doi.org/10.1111/itor.12619

Intl. Trans. in Op. Res. 26 (2019) 1244–1268

DOI: 10.1111/itor.12619

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An efficient local search algorithm with large neighborhoods

for the maximum weighted independent set problem†

Kazuya Haraguchia,∗, Hideki Hashimotob, Junji Itoyanagicand Mutsunori Yagiurad

aFaculty of Commerce,Department of Information and Management Science, Otaru University of Commerce, Midori

3-5-21, Otaru, Hokkaido 0478501, Japan

bDepartment of Logistics and Information Engineering, Tokyo University of Marine Science and Technology, 2-1-6,

Etchujima, Koto-ku, Tokyo 135-8533, Japan

cGraduate School of Information Science, Nagoya University, Furocho,Chikusaku, Nagoya 464-8601, Japan

dDepartment of Mathematical Informatics, GraduateSchool of Informatics, Nagoya University, Furocho,Chikusaku,

Nagoya 464-8601, Japan

E-mail: haraguchi@res.otaru-uc.ac.jp [Haraguchi]; hhashi0@kaiyodai.ac.jp [Hashimoto];

yagiura@nagoya-u.jp[Yagiura]

Received 24 July2017; received in revised form 21 June 2018; accepted 9 November 2018

Abstract

Given an undirected graph G=(V,E)and a weightfor each vertex, the maximum weighted independent set

problem (MWISP) calls fora maximum weight subset Iof Vsuch that no two vertices in Iare 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.

Keywords:maximum weighted independent set problem; iterated local search; large neighborhoods; metaheuristics

1. Introduction

An independent set for a graph is defined as a set of vertices such that no two vertices have an edge

between them. The problem to find the largestindependent set is called the maximum independent set

∗Corresponding author.

†The preliminary version of the paper appeared in Itoyanagi et al. (2011).

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

K. Haraguchi et al. / Intl. Trans.in Op. Res. 26 (2019) 1244–1268 1245

problem (MISP), and the problemto find a maximum weight independent set is called the maximum

weighted independent set problem (MWISP).

Problems MISP and MWISP are known to be NP-hard in general, though MISP is poly-

nomially solvable for some special graph classes such as bipartite graphs, line graphs, claw-free

graphs (Minty, 1980; Nakamura and Tamura, 2001), fork-free graphs (Alekseev, 2004), and perfect

graphs (Gr¨

otschel et al., 1984). Recently, several exact algorithms for MISP are proposed with time

complexity analysis (Bourgeois et al., 2012; Xiao and Nagamochi, 2017). Various approximation

algorithms have been proposed so far for MISP (Halld´

orsson and Radhakrishnan, 1994, 1997;

Halld´

orsson and Yoshihara, 1995), and also for the set packing problem (F¨

urer and Yu, 2014), a

very famous NP-hard problem strongly related to MISP and MWISP.

In order to obtain good solutions within reasonable time, heuristic algorithms have been inten-

sively studied for MISP and MWISP, as well as for two strongly related problems, the minim um

vertex cover proble m and the maximum clique problem, and their weighted versions. Among recent

approaches are a reactive local search (Battiti and Protasi, 2001), a stochastic local search (Pul-

lan and Hoos, 2006), an iterated local search (Grosso et al., 2008), a phased local search

that alternately iterates improvement and plateau search (Pullan, 2009), a parallel hyperheuris-

tic (Pullan et al., 2011), a tabu search method using efficient neighborhood operations (Andrade

et al., 2012), a local search with edge weighting (Cai et al., 2013), a multineighborhood tabu

search (Wu et al., 2012), a breakout local search (Benlic and Hao, 2013), an adaptive multistart tabu

search (Wu and Hao, 2013), and a swap-based multiple neighborhood tabu search (Jin and Hao,

2015).

It is sometimes quite effective to use large neighborhoods in local search algorithms. There are

various types of large neighborhood search (LNS) methods; some use exact methods to search a

neighborhood defined by fixing a part of variables, and others explore a complex neighborhood

using heuristics. Thereis also a sophisticated strategy to design an LNS heuristic, and the algorithms

designed based on this strategy are called very large-scale neighborhood search algorithms (Ahuja

et al., 2002). Searching a large neighborhood is time-consuming if naivelyimplemented, but efficient

search is often realized by incorporating various filtering techniques to limit the search.

In this paper, we propose a new heuristic algorithm that is applicable to both MISP and MWISP.

The algorithm is based on iterated local search,where the local search we treat here is designed upon

(k,)-neighborhood, that is, the set of all solutions obtainable by dropping exactly kvertices from

the current solution and then by adding at most vertices to it.

The main feature of our algorithm is an efficient search method for large neighborhoods using

an exact algorithm, which is incorporated in the local search. Efficient search in the neighborhoods

is realized by restricting the search space without missing improved solutions. The basic part of our

local search is regarded as an extension of Andrade et al.’s (2012) neighborhood search for MISP

to MWISP.

Wetested 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.

The paper is organized as follows. We introduce notation and terminologies in Section 2. In

Section 3, we explain the proposed local search algorithm with large neighborhood. In Section 4,

we present a metaheuristic algorithm based on the iterated local search, which exploits our efficient

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies