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

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

Yun Lu (Department of Mathematics, Kutztown University, Kutztown, PA, USA) and Francis J. Vasko (Department of Mathematics, Kutztown University, Kutztown, PA, USA)
Copyright: © 2015 |Pages: 13
DOI: 10.4018/IJAMC.2015100101


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.
Article Preview

The Set Covering Problem And Proposed Solution Approach

In this section, we will introduce the set covering problem which is a discrete NP-complete (Karp, 1972) combinatorial optimization problem that has many industrial applications. Two important applications from the steel industry are ingot mold selection (Vasko, Wolf and Stott, 1987) and metallurgical grade assignment (Vasko, Wolf and Stott, 1989).

The set covering problem (SCP) is the problem of covering the rows of an m-row, n-column, zero-one matrix (aij) by a subset of the columns at minimum cost. A mathematical formulation for the SCP is:Minimize (1) subject to (2)

(3) where xj is one if column j is in the solution and zero otherwise. Constraint set (2) ensures that each row is covered by at least one column and constraint set (3) ensures that the xj’s take on only the values zero or one.

Since the SCP is NP-complete and industrial applications typically involve large problem instances, many heuristic solution procedures have been developed over the years. For a discussion of recent heuristic and metaheuristic approaches for solving the SCP, we suggest you consult Ren, Feng, Ke and Zhang (2010).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing