Efficiency comparison of exact and approximate algorithms for solving set covering problem

Abstract

Introduction. A quite general class of practical tasks is guided by the set covering problem: schedules building, layout of service stations, and creation of electronic circuits. It defines relevance of searching methods to improve the solution efficiency of this task. Materials and Methods. Techniques of the set covering problem solution by exact and approximate algorithms are considered. The genetic algorithm is used as the approximate method, and the branch and bounds algorithm - as the exact method. Research Results. The genetic algorithm in all its modifications on time response characteristics has shown predictability and stability in all series of experiments. The branch and bounds method was applied to the set covering task, and it has shown exact results. Discussion and Conclusions . The conducted research shows that for small sets, it is expedient to use the branch and bounds method which has demonstrated fast runtime with an assured exact result. For large sets, it is recommended to use the genetic algorithm which guarantees receiving a result with a negligible error where the execution time shift is stable and predictable.

Keywords

• задача покрытия множества
• генетический алгоритм
• модель голдберга
• алгоритм полного перебора
• метод ветвей и границ
• алгоритм алексеева
• set covering problem
• genetic algorithm
• goldberg model
• exhaustive algorithm
• branch-and-bound method
• alekseev algorithm