Evolutionary Search Techniques to Solve Set Covering Problems

Authors: Darwin Gouwanda, S. G. Ponnambalam

Abstract:

Set covering problem is a classical problem in computer science and complexity theory. It has many applications, such as airline crew scheduling problem, facilities location problem, vehicle routing, assignment problem, etc. In this paper, three different techniques are applied to solve set covering problem. Firstly, a mathematical model of set covering problem is introduced and solved by using optimization solver, LINGO. Secondly, the Genetic Algorithm Toolbox available in MATLAB is used to solve set covering problem. And lastly, an ant colony optimization method is programmed in MATLAB programming language. Results obtained from these methods are presented in tables. In order to assess the performance of the techniques used in this project, the benchmark problems available in open literature are used.

Keywords: Set covering problem, genetic algorithm, ant colony optimization, LINGO.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073199

References:

[1] J.E. Beasley and P.C. Chu, "A genetic algorithm for the set covering problem", European Journal of Operational Research, vol. 94, 1996, pp. 392-404
[2] J.E. Beasley, "An algorithm for set covering problem", European Journal of Operational Research, vol. 31, 1987, pp 85-93
[3] J.E. Beasley, "A Lagrangian heuristic for set covering problems", Naval Research Logistics, Vol. 37, 1990, pp. 151-164
[4] S. Haddadi, "Simple Lagrangian heuristic for the set covering problem", European Journal of Operational Research, vol. 97, 1997, pp 200-204
[5] U. Aickelin, "An indirect genetic algorithm for set covering problem" Journal of Operational Research Society, vol. 53, 2002, pp. 1118-1126
[6] A. Monfroglio, "Hybrid heuristic algorithm for set covering", Computers Operational Research, vol. 25, 1998, pp. 441-445
[7] J.F. Vasko and F.E. Wolf, " A heuristic concentration approach for weighted set covering problems", Locator: ePublication of Location Analysis, vol. 2, 2001, no. 1, pp. 1-14
[8] OR-Library: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
[9] E. Balas, and A. Ho, "Set covering algorithms: using cutting planes, heuristics and subgradient optimization: a computational study", Mathematical Programming Study, vol. 12, 1980, pp. 300-304.
[10] Lindo System, Lingo 8.0 user-s manual, 2003
[11] The Mathworks, Matlab-s Genetic Algorithm and Direct Search Toolbox User-s Guide, The Matworks, 2005, Massachusetts
[12] M. Gen, R. Cheng, Genetic Algorithms and Engineering Optimization, John Wiley & Sons, 2000, Canada
[13] L. Lessing, I. Dumitrescu, and T. Stutzle, "A comparison between ACO algorithms for the set covering problem", ANTS 2004, LNCS 3172, 2004, pp. 1-12
[14] M. Rahoual, R. Hadji, and V. Bachelet, "Parallel ant system for the set covering problem" ANTS 2002, LNCS 2463, 2002 pp. 262 - 267.