Premium
Effective heuristics for the Set Covering with Pairs Problem
Author(s) -
Gonçalves Luciana Brugiolo,
De Lima Martins Simone,
Ochi Luiz Satoru
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2010.00768.x
Subject(s) - set cover problem , heuristics , constructive , set (abstract data type) , context (archaeology) , cover (algebra) , mathematical optimization , generalization , greedy algorithm , computer science , mathematics , element (criminal law) , algorithm , engineering , mechanical engineering , paleontology , process (computing) , law , political science , biology , programming language , operating system , mathematical analysis
This paper deals with the Set Covering with Pairs Problem (SCPP). This problem is a generalization of the Set Covering Problem (SCP), which is known to be NP‐hard. The difference between the problems is that, in the SCPP, one element of the universe is admitted to be covered if there are at least two specific objects chosen to cover it. In this context, three constructive heuristics, one local search algorithm and a Greedy Randomized Adaptive Search Procedure are proposed. The algorithms developed were tested in 560 instances available in the literature and they were capable of achieving optimal solutions for several instances.