Effective heuristics for the set covering with pairs problem. (English) Zbl 1220.90107
Summary: 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.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Catanzaro, The pure parsimony haplotyping problem, International Transactions in Operational Research 16 (5) pp 561– (2009) · Zbl 1187.92068 |
| [2] | Chvátal, A greedy heuristic for the set-covering problem, Mathematics of Operations Research 4 pp 233– (1979) |
| [3] | Feo, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 pp 109– (1995) · Zbl 0822.90110 |
| [4] | Fernandes, Microarray synthesis through multiple-use PCR primer design, Bioinformatics 18 pp S128– (2002) · doi:10.1093/bioinformatics/18.suppl_1.S128 |
| [5] | Gusfield, Combinatorial Pattern Matching, Vol. 2676 of Lecture Notes in Computer Science pp 144– (2003) |
| [6] | Hajiaghayi , M.T. Jain , K. Lau , L.C. Mandoiu , I.I. Russell , A. Vazirani , V.V. 2006 Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping Alexandrov , V.N. Van Albada , G.D. Sloot , P.M.A. Dongarra , J.J. Proceedings of the 6th International Conference on Computational Science (ICCS) |
| [7] | Hassin, FSTTCS 2005: Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 3821 of Lecture Notes in Computer Science pp 164– (2005) |
| [8] | Hermelin, The minimum substring cover problem, Information and Computation 206 pp 1303– (2008) · Zbl 1162.90592 |
| [9] | Resende, Metaheuristics: Progress as Real Problem Solvers pp 29– (2005) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
