Evolutionary Search Techniques to Solve Set Covering Problems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:58734", author = "Darwin Gouwanda and S. G. Ponnambalam", title = "Evolutionary Search Techniques to Solve Set Covering Problems", 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.", volume = "2", number = "3", pages = "836-6", }