TítuloThe Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches
Publication TypeConference Proceedings
Year of Conference2017
AuthorsDavidson PPinacho, Blum C, Lozano JAntonio
Conference NameEvoCOP 2017 -- 17th European Conference on Evolutionary Computation in Combinatorial Optimization
Volume10197 (Lecture Notes in Computer Science)
EditorialSpringer Verlag
Paginación201--214
Conference LocationAmsterdam
Resumen

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 theoretical work from the literature, this paper considers the problem from an algorithmic perspective. The first contribution consists in the development of an integer linear programming model and a heuristic that makes use of this model. Second, two greedy heuristics are proposed. Finally, the last contribution is a population-based iterated greedy algorithm that takes profit from the better one of the two developed greedy heuristics. The results of the compared algorithmic approaches show that small problem instances based on random graphs are best solved by an efficient integer linear programming solver such as CPLEX. Larger problem instances are best tackled by the population-based iterated greedy algorithm. The experimental evaluation considers random graphs of different sizes, densities, and ways of generating the node and edge weights.

DOI10.1007/978-3-319-55453-2_14