ils-mwis swMATH ID: 41470 Software Authors: Nogueira, Bruno; Pinheiro, Rian G. S.; Subramanian, Anand Description: A hybrid iterated local search heuristic for the maximum weight independent set problem. This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds. Homepage: https://sites.google.com/site/nogueirabruno/software Keywords: maximum weight independent set; maximum weight clique; minimum weight vertex cover; iterated local search; metaheuristics Related Software: gpuls-mwcp; CUDA; DIMACS; DEAP; PBGL; ilsts-wvcp; NuMVC; SubMAP; scmamp; irace Cited in: 8 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year A hybrid iterated local search heuristic for the maximum weight independent set problem. Zbl 1401.90250Nogueira, Bruno; Pinheiro, Rian G. S.; Subramanian, Anand 2018 all top 5 Cited by 18 Authors 4 Nogueira, Bruno Magalhães 3 Pinheiro, Rian Gabriel S. 1 Blum, Christian 1 Cai, Shaowei 1 Fajardo-Delgado, Daniel 1 Gutierrez-Garcia, J. Octavio 1 Hou, Wenying 1 Li, Yuanjie 1 Lozano, Jose A. 1 Maciel, Paulo 1 Melo, Rafael A. 1 Pinacho Davidson, Pedro 1 Queiroz, Michell F. 1 Santos, Marcio C. 1 Subramanian, Anand Prabhu 1 Tavares, Eduardo Henrique Gomes 1 Trejo-Sánchez, Joel Antonio 1 Wang, Haoran all top 5 Cited in 6 Serials 2 Computers & Operations Research 2 European Journal of Operational Research 1 Information Sciences 1 Annals of Operations Research 1 International Journal of Applied Mathematics and Computer Science 1 Optimization Letters Cited in 3 Fields 6 Operations research, mathematical programming (90-XX) 5 Combinatorics (05-XX) 3 Computer science (68-XX) Citations by Year