Primal and Dual Greedy Heuristics for the Generalized Set Covering Problem

Abstract

This paper reports on the development of primal and dual greedy heuristics for the generalized set covering problem (GSCP). The primal heuristics provide a feasible solution and, consequently, an upper bound on the optimum for the GSCP. Dual based heuristics are used for obtaining and improving lower bounds at optimal value. Both, the primal and dual procedures are described in this paper and the corresponding computational complexity is studied. Moreover, we present empirical results, obtained from computational experience with 34 instances of the GSCP. The test problems are related to the scheduling of bus drivers at Rodoviária Nacional a large transport operator in Portugal. In fact, this specific integer program, GSCP, has been widely used in crew scheduling applications. These computational tests show that a combined primal-dual greedy heuristic procedure is a reasonably accurate and fast tool at least to tackle with bus driver scheduling GSCP instances. Taking into account, another procedure, embedding the primal-dual greedy heuristics in a lagrangean relaxation based method, has been deviced for the GSCP and is presented in a different paper.