A Heuristic Method for the Set Covering Problem

Alberto Caprara, Matteo Fischetti and Paolo Toth
Additional contact information
Alberto Caprara: DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
Matteo Fischetti: DEI, University of Padova, via Gradenigo 61A, 35131 Padova, Italy
Paolo Toth: DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy

Operations Research, 1999, vol. 47, issue 5, 730-743

Abstract: We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and 1,000,000 columns, arising from crew scheduling in the Italian Railway Company, Ferrovie dello Stato SpA. In 1994 Ferrovie dello Stato SpA, jointly with the Italian Operational Research Society, organized a competition, called FASTER, intended to promote the development of algorithms capable of producing good solutions for these instances, since the classical approaches meet with considerable difficulties in tackling them. The main characteristics of the algorithm we propose are (1) a dynamic pricing scheme for the variables, akin to that used for solving large-scale LPs, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain improved solutions. Moreover, we propose a number of improvements on the standard way of defining the step-size and the ascent direction within the subgradient optimization procedure, and the scores within the greedy algorithms. Finally, an effective refining procedure is proposed. Our code won the first prize in the FASTER competition, giving the best solution value for all the proposed instances. The algorithm was also tested on the test instances from the literature: in 92 out of the 94 instances in our test bed we found, 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 techniques.

Keywords: programming; integer; set covering; heuristic algorithm (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (64)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.5.730 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:5:p:730-743

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().