An electromagnetism metaheuristic for the unicost set covering problem

Zahra Naji-Azimi, Paolo Toth and Laura Galli

European Journal of Operational Research, 2010, vol. 205, issue 2, 290-300

Abstract: In this paper we propose a new heuristic algorithm to solve the unicost version of the well-known set covering problem. The method is based on the electromagnetism metaheuristic approach which, after generating a pool of solutions to create the initial population, applies a fixed number of local search and movement iterations based on the "electromagnetism" theory. In addition to some random aspects, used in the construction and local search phases, we also apply mutation in order to further escape from local optima. The proposed algorithm has been tested over 80 instances of the literature. On the classical benchmark instances, where the number of columns is larger than the number of rows, the algorithm, by using a fixed set of parameters, always found the best known solution, and for 12 instances it was able to improve the current best solution. By using different parameter settings the algorithm improved 4 additional best known solutions. Moreover, we proved the effectiveness of the electromagnetism metaheuristic approach for the unicost set covering problem by embedding the procedures of the proposed algorithm in a genetic algorithm scheme. The worse results obtained by the genetic algorithm show the impact of the electromagnetism metaheuristic approach in conducting the search of the solution space by applying the movements based on the electromagnetism theory. Finally, we report the results obtained by modifying the proposed electromagnetism metaheuristic algorithm for solving the non-unicost set covering problem.

Keywords: Combinatorial; optimization; Unicost; set; covering; problem; Electromagnetism; metaheuristic (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00043-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:205:y:2010:i:2:p:290-300

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().