An OR Practitioner's Solution Approach for the Set Covering Problem

Yun Lu and Francis J. Vasko
Additional contact information
Yun Lu: Department of Mathematics, Kutztown University, Kutztown, PA, USA
Francis J. Vasko: Department of Mathematics, Kutztown University, Kutztown, PA, USA

International Journal of Applied Metaheuristic Computing (IJAMC), 2015, vol. 6, issue 4, 1-13

Abstract: The set covering problem (SCP) is an NP-complete problem that has many important industrial applications. Since industrial applications are typically large in scale, exact solution algorithms are not feasible for operations research (OR) practitioners to use when called on to solve real-world problems involving SCPs. However, the best performing heuristics for the SCP reported in the literature are not usually straightforward to implement. Additionally, these heuristics usually require the fine-tuning of several parameters. In contrast, simple greedy or even randomized greedy heuristics typically do not give as good results as the more sophisticated heuristics. In this paper, the authors present a compromise; a straightforward to implement, population-based solution approach for the SCP. It uses a randomized greedy approach to generate an initial population and then uses a genetic-based two phase approach to improve the population solutions. This two-phase approach uses transformation equations based on a Teaching-Learning based optimization approach developed by Rao, Savsani and Vakharia (2011, 2012) for continuous nonlinear optimization problems. Empirical results using set covering problems from Beasley's OR-library demonstrate the competitiveness of this approach both in terms of solution quality and execution time. The advantage to this approach is its relative simplicity for the practitioner to implement.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJAMC.2015100101 (application/pdf)

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:igg:jamc00:v:6:y:2015:i:4:p:1-13

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().