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

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

Yun Lu, Francis J. Vasko
Copyright: © 2015 |Pages: 13
DOI: 10.4018/IJAMC.2015100101
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

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

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 IJAMC.2015100101.m01(1) subject to IJAMC.2015100101.m02(2)

IJAMC.2015100101.m03
(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:
Reset
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
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