Efficiency comparison of exact and approximate algorithms for solving set covering problem
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. Techniq...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Don State Technical University
2017-10-01
|
| Series: | Advanced Engineering Research |
| Subjects: | |
| Online Access: | https://www.vestnik-donstu.ru/jour/article/view/174 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849250632251211776 |
|---|---|
| author | Igor S. Konovalov Sergey S. Ostapenko Valery G. Kobak |
| author_facet | Igor S. Konovalov Sergey S. Ostapenko Valery G. Kobak |
| author_sort | Igor S. Konovalov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-76db3e24714d413694c5a3340b367a24 |
| institution | Kabale University |
| issn | 2687-1653 |
| language | Russian |
| publishDate | 2017-10-01 |
| publisher | Don State Technical University |
| record_format | Article |
| series | Advanced Engineering Research |
| spelling | doaj-art-76db3e24714d413694c5a3340b367a242025-08-20T03:57:12ZrusDon State Technical UniversityAdvanced Engineering Research2687-16532017-10-0117313714410.23947/1992-5980-2017-17-3-137-144174Efficiency comparison of exact and approximate algorithms for solving set covering problemIgor S. Konovalov0Sergey S. Ostapenko1Valery G. Kobak2Don State Technical UniversityDon State Technical UniversityDon State Technical UniversityIntroduction. 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.https://www.vestnik-donstu.ru/jour/article/view/174задача покрытия множествагенетический алгоритммодель голдбергаалгоритм полного перебораметод ветвей и границалгоритм алексееваset covering problemgenetic algorithmgoldberg modelexhaustive algorithmbranch-and-bound methodalekseev algorithm |
| spellingShingle | Igor S. Konovalov Sergey S. Ostapenko Valery G. Kobak Efficiency comparison of exact and approximate algorithms for solving set covering problem Advanced Engineering Research задача покрытия множества генетический алгоритм модель голдберга алгоритм полного перебора метод ветвей и границ алгоритм алексеева set covering problem genetic algorithm goldberg model exhaustive algorithm branch-and-bound method alekseev algorithm |
| title | Efficiency comparison of exact and approximate algorithms for solving set covering problem |
| title_full | Efficiency comparison of exact and approximate algorithms for solving set covering problem |
| title_fullStr | Efficiency comparison of exact and approximate algorithms for solving set covering problem |
| title_full_unstemmed | Efficiency comparison of exact and approximate algorithms for solving set covering problem |
| title_short | Efficiency comparison of exact and approximate algorithms for solving set covering problem |
| title_sort | efficiency comparison of exact and approximate algorithms for solving set covering problem |
| topic | задача покрытия множества генетический алгоритм модель голдберга алгоритм полного перебора метод ветвей и границ алгоритм алексеева set covering problem genetic algorithm goldberg model exhaustive algorithm branch-and-bound method alekseev algorithm |
| url | https://www.vestnik-donstu.ru/jour/article/view/174 |
| work_keys_str_mv | AT igorskonovalov efficiencycomparisonofexactandapproximatealgorithmsforsolvingsetcoveringproblem AT sergeysostapenko efficiencycomparisonofexactandapproximatealgorithmsforsolvingsetcoveringproblem AT valerygkobak efficiencycomparisonofexactandapproximatealgorithmsforsolvingsetcoveringproblem |