A heuristic method for the set covering problem

We present a Lagrangian-based heuristic for the well-known Set Covering Pro blem (SCP). The algorithm was initially designed for solving very large sca le SCP instances, involving up to 5,000 rows and 1,000,000 columns, arising from crew scheduling in the Italian Railway Company, Ferrovie dello State SpA. In 1994 Ferrovie dello State SpA, jointly with the Italian Operational Research Society, organized a competition, called FASTER, intended to prom ote the development of algorithms capable of producing good solutions for t hese instances, since the classical approaches meet with considerable diffi culties in tackling them. The main characteristics of the algorithm we prop ose are (1) a dynamic pricing scheme for the variables, akin to that used f or solving large-scale LPs, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain i mproved solutions. Moreover, we propose a number of improvements on the sta ndard way of defining the step-size and the ascent direction within the sub gradient optimization procedure, and the scores within the greedy algorithm s. Finally, an effective refining procedure is proposed. Our code won the f irst prize in the FASTER competition, giving the best solution value for al l the proposed instances. The algorithm was also tested on the test instanc es from the literature: in 92 out of the 94 instances in our test bed we fo und, within short computing time, the optimal (or the best known) solution. Moreover, among the 18 instances for which the optimum is not known, in 6 cases our solution is better than any other solution found by previous tech niques.