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 -