Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A morphing procedure to supplement a simulated annealing heuristic for cost‐ andcoverage‐correlated set‐covering problems

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

Abstract

We report on the use of a morphing procedure in a simulated annealing (SA) heuristicdeveloped for set‐covering problems (SCPs). Morphing enables the replacement of columnsin solution with similar but more effective columns (morphs). We developed this procedureto solve minimum cardinality set‐covering problems (MCSCPs) containing columns whichexhibit high degrees of coverage correlation, and weighted set‐covering problems (WSCPs)that exhibit high degrees of both cost correlation and coverage correlation. Such correlationstructures are contained in a wide variety of real‐world problems including many scheduling,design, and location applications. In a large computational study, we found that the morphingprocedure does not degrade the performance of an SA heuristic for SCPs with low degreesof cost and coverage correlation (given a reasonable amount of computation time), and thatit improves the performance of an SA heuristic for problems with high degrees of suchcorrelations.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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, Cutting planes from conditional bounds: A new approach to set covering, Mathematical Programming Study 12(1980)19-36.

    Google Scholar 

  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. ]E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, Mathematical Programming Study 12(1980)37-60.

    Google Scholar 

  4. E. Balas and S.M. Ng, On the set covering polytope: I. All the facets with coefficients in 0, 1, 2, Mathematical Programming 43(1989)57-69.

    Google Scholar 

  5. E. Balas and S.M. Ng, On the set covering polytope: II. Lifting all the facets with coefficients in 0, 1, 2, Mathematical Programming 45(1989)1-20.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  8. 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 

  9. 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 

  10. J. Bouliane and G. Laporte, Locating postal relay boxes using a set covering algorithm, American Journal of Mathematical and Management Sciences 12(1992)65-74.

    Google Scholar 

  11. G.B. Brown, G.W. Graves and D. Ronen, Scheduling ocean transportation of crude oil, Management Science 33(1987)335-346.

    Google Scholar 

  12. M.J. Brusco and L.W. Jacobs, A simulated annealing approach to the cyclic staff-scheduling problem, Naval Research Logistics 40(1993)69-84.

    Google Scholar 

  13. M.J. Brusco, L.W. Jacobs, R.J. Bongiorno, D.V. Lyons and B. Tang, Improving personnel scheduling at airline stations, Operations Research 43(1995)741-751.

    Google Scholar 

  14. A. Caprara, M. Fischetti and P. Toth, A heuristic algorithm for the set covering problem, Lecture Notes in Computer Science, vol. 1084, 1996, pp. 72-84.

  15. S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Working Paper, University of Roma La Sapienza, Italy, 1995.

    Google Scholar 

  16. V. Cerny, Thermodynamical approach to the traveling salesman problem, Journal of Optimization Theory and Applications 45(1985)41-51.

    Google Scholar 

  17. V. Chvatal, A greedy heuristic for the set covering problem, Mathematics of Operations Research 4(1979)233-235.

    Google Scholar 

  18. J. Current and M. O'Kelly, Locating emergency warning sirens, Decision Sciences 23(1992)221-234.

    Google Scholar 

  19. R.H. Day, On optimal extracting from a multiple file data storage system: An application of integer programming, Operations Research 13(1965)482-494.

    Google Scholar 

  20. J. Dongarra, Linpack Benchmark, URL — http://ap01.physik.uni-greifswald.de/~ftp/bench/linpack.html, October 2, 1995.

  21. J. Etcheberry, The set covering problem: A new implicit enumeration algorithm, Operations Research 25(1977)760-772.

    Google Scholar 

  22. M.L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems, Management Science 36(1990)674-688.

    Google Scholar 

  23. M.L. Fisher and M.B. Rosenwein, An interactive optimization system for bulk cargo ship scheduling, Naval Research Logistics 36(1989)27-42.

    Google Scholar 

  24. J. Gleason, A set covering approach to bus stop location, Omega 3(1975)605-608.

    Google Scholar 

  25. G.W. Graves, R.D. McBride, I. Gershkoff, D. Anderson and D. Mahidhara, Flight crew scheduling, Management Science 39(1993)736-745.

    Google Scholar 

  26. F. Harche and G.L. Thompson, The column subtraction algorithm: An exact method for solving weighted set covering, packing, and partitioning problems, Computers and Operations Research 21(1994)698-706.

    Google Scholar 

  27. ]A.M. Hey and N. Christofides, Algorithms for the set covering problem using graph theory, Working Paper, Imperial College, London, England, 1993.

    Google Scholar 

  28. K.L. Hoffman and M. Padberg, Solving airline crew scheduling problems by branch-and-cut, Management Science 39(1993)657-682.

    Google Scholar 

  29. J. Holmes, F.B. Williams and L.A. Brown, Facility location under a maximum travel restriction: An example using day care facilities, Geographical Analysis 4(1972)258-266.

    Google Scholar 

  30. L.W. Jacobs and M.J. Brusco, Note: A local-search heuristic for large set-covering problems, Naval Research Logistics 42(1995)1129-1140.

    Google Scholar 

  31. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation; Part I, Graph partitioning, Operations Research 37(1989)865-892.

    Google Scholar 

  32. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation; Part II, Graph coloring by number partitioning, Operations Research 39(1991)378-406.

    Google Scholar 

  33. D.J. Jones, M.A. Beltramo and M.S. Daskin, A metaheuristic for large set-covering problems, Working Paper, General Motors R&D Center, Warren, MI, 1994.

    Google Scholar 

  34. R.M. Karp, in: Complexity of Computer Computations, eds. R.E. Miller and J.W. Thatcher, Plenum Press, New York, 1972.

    Google Scholar 

  35. S. Kirkpatrick, C.D. Gelatt, Jr. and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671-683.

    Google Scholar 

  36. C.E. Lemke, H.M. Salkin and K. Spielberg, Set covering by single branch enumeration with linear programming subproblems, Operations Research 19(1971)998-1022.

    Google Scholar 

  37. 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 

  38. N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A. Teller and E. Teller, Equation of state calculations by fast computing machines, Journal of Chemical Physics 21(1953)1087-1092.

    Google Scholar 

  39. R.A. Rushmeier and G.L. Nemhauser, Experiments with parallel branch-and bound algorithms for the set covering problem, Operations Research Letters 13(1993)277-286.

    Google Scholar 

  40. H.M. Salkin and R.D. Koncal, Set covering by an all integer algorithm: Computational experience, Journal of the Association for Computing Machinery 31(1973)336-345.

    Google Scholar 

  41. B.M. Smith, IMPACS — A bus crew scheduling system using integer programming, Mathematical Programming 42(1988)181-187.

    Google Scholar 

  42. G. Thompson, A simulated-annealing heuristic for shift scheduling using non-continuously available employees, Computers and Operations Research 23(1996)275-288.

    Google Scholar 

  43. C. Torregas, R. Swain, C. ReVelle and L. Bergman, The location of emergency service facilities, Operations Research 19(1971)1363-1373.

    Google Scholar 

  44. F.J. Vasko and G.R. Wilson, Hybrid heuristics for minimum-cardinality set covering problems, Naval Research Logistics Quarterly 33(1986)241-249.

    Google Scholar 

  45. F.J. Vasko and G.R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly 31(1984)163-171.

    Google Scholar 

  46. F.J. Vasko and F.E. Wolf, Solving large set-covering problems on a personal computer, Computers and Operations Research 15(1988)115-121.

    Google Scholar 

  47. F.J. Vasko, F.E. Wolf and K.L. Stott, Optimal selection of ingot sizes via set covering, Operations Research 35(1987)346-353.

    Google Scholar 

  48. ]W. Walker, Application of the set covering problem to the assignment of ladder trucks to fire houses, Operations Research 22(1974)275-277.

    Google Scholar 

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

    Google Scholar 

Download references

Authors
  1. M.J. Brusco
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. L.W. Jacobs
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. G.M. Thompson
    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

Brusco, M., Jacobs, L. & Thompson, G. A morphing procedure to supplement a simulated annealing heuristic for cost‐ andcoverage‐correlated set‐covering problems. Annals of Operations Research 86, 611–627 (1999). https://doi.org/10.1023/A:1018900128545

Download citation

  • Issue Date:

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

Keywords

Search

Navigation