A Genetic Algorithm for the Set Covering Problem

Abstract

In this paper, the set covering problem (SCP) is considered. Several algorithms have been suggested in the literature for solving it. We propose a new algorithm for solving the SCP which is based on the genetic technique. This algorithm has been implemented and tested on various standard and randomly generated test problems. Preliminary results are encouraging, and are better than the existing heuristics for the problem.

Keywords:

• Chvatal's algorithm
• genetic algorithm
• implicit enumeration
• Lagrangian heuristic
• NP-complete problem
• set-covering problem
• 0–1 integer programs