| Article ID: | iaor20107464 |
| Volume: | 17 |
| Issue: | 6 |
| Start Page Number: | 739 |
| End Page Number: | 751 |
| Publication Date: | Nov 2010 |
| Journal: | International Transactions in Operational Research |
| Authors: | Gonalves Luciana Brugiolo, de Lima Martins Simone, Ochi Luiz Satoru |
| Keywords: | sets |
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.