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. 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.

Задача покрытия множества, генетический алгоритм, модель Голдберга, алгоритм полного перебора, метод ветвей и границ, алгоритм Алексеева, set covering problem, genetic algorithm, Goldberg model, exhaustive algorithm, branch-and-bound method, Alekseev algorithm

1. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Sravnitel'nyy analiz raboty zhadnogo algoritma Khvatala i modifitsirovannoy modeli Goldberga pri reshenii vzveshennoy zadachi nakhozhdeniya minimal'nogo pokrytiya mnozhestv. [Comparative analysis of work of Chvatal greedy algorithm and modified Goldberg model under solving the problem on determining minimal set covering.] Trudy SKF MTUSI. Rostov-on-Don: PTs «Universitet» SKF MTUSI, 2015, pp. 366–371 (in Russian).

2. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Strategiya elitizma modifitsirovannoy modeli Goldberga geneticheskogo algoritma pri reshenii zadachi pokrytiya mnozhestv. [Elitism strategy of modified Goldberg model of genetic algorithm in solving the set covering problem.] Herald of Computer and Information Technologies, 2016, no. 4, pp. 50–56 (in Russian).

3. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Primenenie geneticheskogo algoritma dlya resheniya zadachi pokrytiya mnozhestv. [Application of genetic algorithm for the set-covering problem solution.] Vestnik of DSTU, 2016, no. 3pp. 125–132 (in Russian).

4. Eremeev, A.V. Geneticheskiy algoritm dlya zadachi o pokrytii. [A genetic algorithm for the covering problem.] Discrete Analysis and Operations Research, 2000, ser. 2, vol. 7, no. 1, pp. 47–60 (in Russian).

5. Eremeev, A.V., Zaozerskaya, L.A., Kolokolov, A.A. Zadacha o pokrytii mnozhestva: slozhnost', algoritmy, eksperimental'nye issledovaniya. [The set covering problem: complexity, algorithms, and experimental investigations.] Discrete Analysis and Operations Research, 2000, ser.2, vol. 7, no. 2, pp. 22–47 (in Russian).

6. Holland, J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975, p. 245.

7. Goldberg, D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989, p. 432.

8. Batishchev, D.I. Geneticheskie algoritmy resheniya ekstremal'nykh zadach. [Genetic algorithms for solving extremal problems.] Voronezh: izd-vo Voronezh. gos. tekhn. un-ta, 1995, 121 p. (in Russian).

9. Gladkov, L.A., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Gtnetic algorithms.] Moscow: FIZMATLIT, 2010, 368 p. (in Russian).

10. Alekseev, O.G., Grigoryev, V.F. Nekotorye algoritmy resheniya zadachi o pokrytii i ikh eksperimental'noe issledovanie na EVM. [Some algorithms for solving the covering problem and their experimental computed study.] Computational Mathematics and Mathematical Physics, 1984, vol. 24, no. 10, pp. 1565–1570 (in Russian).