Iterated local search for the generalized independent set problem
- PDF / 397,444 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 243 Views
Iterated local search for the generalized independent set problem Bruno Nogueira1
· Rian G. S. Pinheiro1 · Eduardo Tavares2
Received: 15 November 2019 / Accepted: 2 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The generalized independent set problem (GISP) can be conceived as a relaxation of the maximum weight independent set problem. GISP has a number of practical applications, such as forest harvesting and handling geographic uncertainty in spatial information. This work presents an iterated local search (ILS) heuristic for solving GISP. The proposed heuristic relies on two new neighborhood structures, which are explored using a variable neighborhood descent procedure. Experimental results on a well-known GISP benchmark indicate our proposal outperforms the best existing heuristic for the problem. In particular, our ILS approach was able to find all known optimal solutions and to present new improved best solutions. Keywords Combinatorial optimization · Maximum independent set · Iterated local search · Variable neighborhood descent · Metaheuristics
1 Introduction Consider an undirected graph G = (V , E), a subset of removable edges E ⊆ E, revenues b(vi ) for each vertex vi ∈ V , and costs c(vi , v j ) for each removable edge (vi , v j ) ∈ E . The generalized independent set problem (GISP) aims at determining an independent set S ⊆ V (i.e., a subset of vertices such that no two vertices are adjacent) that maximize the profit, defined as the difference between selected vertex
B
Bruno Nogueira bruno@ic.ufal.br Rian G. S. Pinheiro rian@ic.ufal.br Eduardo Tavares eagt@cin.ufpe.br
1
Universidade Federal de Alagoas, Instituto de Computacão, Maceió, Brazil
2
Universidade Federal de Pernambuco, Centro de Informática, Recife, Brazil
123
B. Nogueira et al.
v7
v6 v8
v5
v4
v3
v2 v1
Fig. 1 The generalized independent set problem: instance and candidate solution
revenues and the total cost of deleting removable edges connecting them. GISP can be conceived as a relaxation of the well-known maximum weight independent set (MWIS) problem [1], i.e., it allows adjacent vertices to be in the independent set but take into account the penalties of doing so. Due to this property, the GISP model has potential to be applied to many practical applications, such as: forest harvesting [2], handling geographic uncertainty in spatial information [3], facility location [4], and cartographic label placement [5]. Figure 1 shows an instance of the GISP, and a candidate solution. Dashed edges indicate the set of removable edges E and gray vertices the set of solution vertices S. The profit of this solution is calculated as: b(v2 ) + b(v3 ) + b(v6 ) + b(v8 ) − c(v2 , v6 ). GISP is computationally challenging since it belongs to the class of N P-hard problems. As a consequence, current exact methods [2,6,7] for the problem are efficient only on instances of limited sizes or instances with particular structures. In this work, we focus on heuristic methods that seek high-quality sub-opti
Data Loading...
