TY - UNPB
T1 - Exploiting Domain Structures in Heuristic Algorithms for the Set Covering Problem
T2 - A Literature Review
AU - Babatunde, Abiola
PY - 2022/4/1
Y1 - 2022/4/1
N2 - This review aims at understanding the set covering problem (SCP) as an NP-hard problem, the variants of SCP, the methods that have been proposed to solve the problem, and gaps in the existing solutions that have been provided which need further research. A polynomial time algorithm to give an optimal solution to the Set Covering Problem is only possible if P=NP and so we do not expect to find such an algorithm. Instead, various heuristic algorithms have been used in an attempt to find an optimal solution for the problem. Exploring these types of algorithms provides solutions that are usable, or near optimal, but not exact which reduces the computational cost for the set covering problem. A comparison of metaheuristic algorithms and optimization of these algorithms is explored in this review
AB - This review aims at understanding the set covering problem (SCP) as an NP-hard problem, the variants of SCP, the methods that have been proposed to solve the problem, and gaps in the existing solutions that have been provided which need further research. A polynomial time algorithm to give an optimal solution to the Set Covering Problem is only possible if P=NP and so we do not expect to find such an algorithm. Instead, various heuristic algorithms have been used in an attempt to find an optimal solution for the problem. Exploring these types of algorithms provides solutions that are usable, or near optimal, but not exact which reduces the computational cost for the set covering problem. A comparison of metaheuristic algorithms and optimization of these algorithms is explored in this review
KW - Set covering problem
KW - NP-completeness
KW - optimization
KW - metaheuristic algorithm
M3 - Working paper
T3 - NA
BT - Exploiting Domain Structures in Heuristic Algorithms for the Set Covering Problem
ER -