dc.contributor.author Pinacho Davidson P. en_US dc.contributor.author Blum C. en_US dc.contributor.author Lozano J.A. en_US dc.date.accessioned 2017-08-30T14:23:21Z dc.date.available 2017-08-30T14:23:21Z dc.date.issued 2017-08-30 dc.identifier.issn 0377-2217 dc.identifier.uri http://hdl.handle.net/20.500.11824/727 dc.description.abstract This work deals with the so-called weighted independent domination problem, which is an $NP$-hard combinatorial optimization problem in graphs. In contrast to previous work, this paper considers the problem from a non-theoretical perspective. The first contribution consists in the development of three integer linear programming models. Second, two greedy heuristics are proposed. Finally, the last contribution is a population-based iterated greedy metaheuristic which is applied in two different ways: (1) the metaheuristic is applied directly to each problem instance, and (2) the metaheuristic is applied at each iteration of a higher-level framework---known as construct, merge, solve \& adapt---to sub-instances of the tackled problem instances. The results of the considered algorithmic approaches show that integer linear programming approaches can only compete with the developed metaheuristics in the context of graphs with up to 100 nodes. When larger graphs are concerned, the application of the populated-based iterated greedy algorithm within the higher-level framework works generally best. The experimental evaluation considers graphs of different types, sizes, densities, and ways of generating the node and edge weights. en_US dc.format application/pdf en_US dc.language.iso eng en_US dc.publisher European Journal of Operational Research en_US dc.relation ES/1PE/SEV-2013-0323 en_US dc.relation EUS/BERC/BERC.2014-2017 en_US dc.relation EUS/ELKARTEK en_US dc.rights info:eu-repo/semantics/openAccess en_US dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/es/ en_US dc.title The Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches en_US dc.type info:eu-repo/semantics/article en_US dc.type info:eu-repo/semantics/acceptedVersion en_US
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as info:eu-repo/semantics/openAccess