Skip to main content
SpringerLink
Log in

Algorithms for the Set Covering Problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Balas, A class of location, distribution and scheduling problems: Modeling and solution methods, in: Proceedings of the Chinese-U.S. Symposium on Systems Analysis, eds. P. Gray and L. Yuanzhang (Wiley, 1983).

  2. E. Balas and M.C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research 44 (1996) 875–890.

    Google Scholar 

  3. J.E. Beasley, An algorithm for set covering problems, European Journal of Operational Research 31 (1987) 85–93.

    Google Scholar 

  4. J.E. Beasley, A Lagrangian heuristic for set covering problems, Naval Research Logistics 37 (1990) 151–164.

    Google Scholar 

  5. J.E. Beasley, OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society 41 (1990) 1069–1072.

    Google Scholar 

  6. J.E. Beasley and P.C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research 94 (1996) 392–404.

    Google Scholar 

  7. J.E. Beasley and K. Jörnsten, Enhancing an algorithm for set covering problems, European Journal of Operational Research 58 (1992) 293–300.

    Google Scholar 

  8. M.J. Brusco, L.W. Jacobs and G.M. Thompson, A morphing procedure to supplement a simulated annealing heuristic for cost-and coverage-correlated weighted set-covering problems, Annals of Operations Research 86 (1999) 611–627.

    Google Scholar 

  9. A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Operations Research 47 (1999) 730–743.

    Google Scholar 

  10. A. Caprara, M. Fischetti and P. Toth, Effective solution of the LP relaxation of set covering problems, Working Paper, DEIS, University of Bologna (1998).

  11. A. Caprara, M. Fischetti, P. Toth, D. Vigo and P.L. Guida, Algorithms for railway crew management, Mathematical Programming 79 (1997) 125–141.

    Google Scholar 

  12. S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming 81 (1998) 215–228.

    Google Scholar 

  13. S. Ceria, P. Nobili and A. Sassano, Set covering problem, in: Annotated Bibliographies in Combinatorial Optimization, eds. M. Dell'Amico, F. Maffioli and S. Martello (Wiley, 1997) pp. 415–428.

  14. H.D. Chu, E. Gelman and E.L. Johnson, Solving large scale crew scheduling problems, European Journal of Operational Research 97 (1997) 260–268.

    Google Scholar 

  15. J.J. Dongarra, Performance of various computers using standard linear equations software, Technical Report No. CS–89–85, Computer Science Department, University of Tennessee (1996).

  16. M.L. Fisher, An applications oriented guide to Lagrangian optimization, Interfaces 15 (1985) 10–21.

    Google Scholar 

  17. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman, 1979).

  18. S. Haddadi, Simple Lagrangian heuristic for the set covering problem, European Journal of Operational Research 97 (1997) 200–204.

    Google Scholar 

  19. M. Held and R.M. Karp, The traveling salesman problem and minimum spanning trees: Part II, Mathematical Programming 1 (1971) 6–25.

    Google Scholar 

  20. L.W. Jacobs and M.J. Brusco, A local search heuristic for large set-covering problems, Naval Research Logistics 52 (1995) 1129–1140.

    Google Scholar 

  21. L.A.N. Lorena and F.B. Lopes, A surrogate heuristic for set covering problems, European Journal of Operational Research 79 (1994) 138–150.

    Google Scholar 

  22. C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM 41 (1994) 960–981.

    Google Scholar 

  23. S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations (Wiley, 1990).

  24. P. Nobili and A. Sassano, A separation routine for the set covering polytope, in: Integer Programming and Combinatorial Optimization, eds. E. Balas, G. Cornuejols and R. Kannan, Proceedings of the 2nd IPCO Conference (Carnegie-Mellon University Press, 1992).

  25. K.S. Al-Sultan, M.F. Hussain and I.S. Nizami, A genetic algorithm for the set covering problem, Journal of the Operational Research Society 47 (1996) 702–709.

    Google Scholar 

  26. D. Wedelin, An algorithm for large scale 0–1 integer programming with application to airline crew scheduling, Annals of Operations Research 57 (1995) 283–301.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DEIS, University of Bologna, Viale Risorgimento 2, I-40136, Bologna, Italy

    Alberto Caprara & Paolo Toth

  2. DEI, University of Padova, Via Gradenigo 6/A, I-35131, Padova, Italy

    Matteo Fischetti

Authors
  1. Alberto Caprara
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paolo Toth
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matteo Fischetti
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Caprara, A., Toth, P. & Fischetti, M. Algorithms for the Set Covering Problem. Annals of Operations Research 98, 353–371 (2000). https://doi.org/10.1023/A:1019225027893

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019225027893

Keywords

Search

Navigation