The Impact of a New Formulation When Solving the Set Covering Problem Using the ACO Metaheuristic

1. Balachandar, S.R., Kannan, K.: A meta-heuristic algorithm for set covering problem based on gravity 4(7), 944–950 (2010)

   Google Scholar 

2. Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research 44(6), 875–890 (1996)

   Article  MATH  MathSciNet  Google Scholar 

3. Beasley, J.E.: Or-library: distributing test problems by electronic mail. Journal of the Operational Research Society 41(11), 1069–1072 (1990)

   Article  Google Scholar 

4. Beasley, J., Chu, P.: A genetic algorithm for the set covering problem. European Journal of Operational Research 94(2), 392–404 (1996)

   Article  MATH  Google Scholar 

5. Brusco, M., Jacobs, L., Thompson, G.: A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems. Annals of Operations Research 86, 611–627 (1999)

   Article  MATH  MathSciNet  Google Scholar 

6. Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set covering problem. Operations Research 47(5), 730–743 (1999)

   Article  MATH  MathSciNet  Google Scholar 

7. Caserta, M.: Tabu search-based metaheuristic algorithm for large-scale set covering problems. In: Doerner, K., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R., Reimann, M. (eds.) Metaheuristics, Operations Research/Computer Science Interfaces Series, vol. 39, pp. 43–63. Springer US (2007)

   Google Scholar 

8. Ceria, S., Nobili, P., Sassano, A.: A lagrangian-based heuristic for large-scale set covering problems. Mathematical Programming 81(2), 215–228 (1998)

   Article  MATH  MathSciNet  Google Scholar 

9. Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 233–235 (1979)

   Article  MATH  MathSciNet  Google Scholar 

10. Crawford, B., Soto, R., Monfroy, E., Castro, C., Palma, W., Paredes, F.: A hybrid soft computing approach for subset problems. Mathematical Problems in Engineering, Article ID 716069, 1–12 (2013)

    Google Scholar 

11. Crawford, B., Castro, C.: Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. In: Rutkowski, L., Tadeusiewicz, R., Zadeh, L.A., Żurada, J.M. (eds.) ICAISC 2006. LNCS (LNAI), vol. 4029, pp. 1082–1090. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

12. Crawford, B., Castro, C., Monfroy, E.: A hybrid ant algorithm for the airline crew pairing problem. In: Gelbukh, A., Reyes-Garcia, C.A. (eds.) MICAI 2006. LNCS (LNAI), vol. 4293, pp. 381–391. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

13. Crawford, B., Lagos, C., Castro, C., Paredes, F.: A evolutionary approach to solve set covering. In: ICEIS (2), pp. 356–363 (2007)

    Google Scholar 

14. Crawford, B., Soto, R., Monfroy, E.: Cultural algorithms for the set covering problem. In: ICSI (2), pp. 27–34 (2013)

    Google Scholar 

15. Dorigo, M., Gambardella, L.M.: Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)

    Article  Google Scholar 

16. Dorigo, M., Stutzle, T.: Ant Colony Optimization. MIT Press, USA (2004)

    Google Scholar 

17. Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B 26(1), 29–41 (1996)

    Article  Google Scholar 

18. Fisher, M.L., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Management Science 36(6), 674–688 (1990)

    Article  MATH  MathSciNet  Google Scholar 

19. Hadji, R., Rahoual, M., Talbi, E., Bachelet, V.: Ant colonies for the set covering problem. In: Dorigo, M., et al. (eds.) ANTS 2000, pp. 63–66 (2000)

    Google Scholar 

20. Leguizamón, G., Michalewicz, Z.: A new version of ant system for subset problems. In: Angeline, P., Michalewicz, Z., Schoenauer, M., Yao, X., Zalzala, A. (eds.) Proceedings of Congress on Evolutionary Computation (CEC 1999), July 6-9. IEEE Press, Washington, DC (1999)

    Google Scholar 

21. Lessing, L., Dumitrescu, I., Stützle, T.: A comparison between ACO algorithms for the set covering problem. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 1–12. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

22. Mesquita, M., Paias, A.: Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Computers and Operations Research 35(5), 1562–1575 (2008), part Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility

    Google Scholar 

23. Mohan, B.C., Baskaran, R.: A survey: Ant colony optimization based recent research and implementation on several engineering domain. Expert Systems with Applications 39(4), 4618–4627 (2012)

    Article  Google Scholar 

24. Naji-Azimi, Z., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost set covering problem. European Journal of Operational Research 205(2), 290–300 (2010)

    Article  MATH  MathSciNet  Google Scholar 

25. Nehme, B., Galinier, P., Guibault, F.: A new formulation of the set covering problem for metaheuristic approaches. ISRN Operations Research, Article ID 203032, 1–10 (2013)

    Google Scholar 

26. Ren, Z.G., Feng, Z.R., Ke, L.J., Zhang, Z.J.: New ideas for applying ant colony optimization to the set covering problem. Computers and Industrial Engineering 58(4), 774–784 (2010)

    Article  Google Scholar 

27. Vasko, F.J., Wolf, F.E., Stott, K.L.: Optimal selection of ingot sizes via set covering. Operations Research 35(3), 346–353 (1987)

    Article  Google Scholar 

28. Vasko, F.J., Wilson, G.R.: Using a facility location algorithm to solve large set covering problems. Operations Research Letters 3(2), 85–90 (1984)

    Article  MATH  Google Scholar 

Download references