Skip to main content
SpringerLink
Log in

A Teaching-Learning-Based Optimization Algorithm for Solving Set Covering Problems

  • Conference paper
  • First Online:
Computational Science and Its Applications -- ICCSA 2015 (ICCSA 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9158))

Included in the following conference series:

Abstract

The Set Covering Problem (SCP) is a representation of a kind of combinatorial optimization problem which has been applied in several problems in the real world. In this work we used a binary version of Teaching-Learning-Based Optimization (TLBO) algorithm to solve SCP, works with two phases known: teacher and learner; emulating the behavior into a classroom. The proposed algorithm has been tested on 65 benchmark instances. The results show that it has the ability to produce solutions competitively.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Amini, F., Ghaderi, P.: Hybridization of harmony search and ant colony optimization for optimal locating of structural dampers. Appl. Soft Comput. 13(5), 2272–2280 (2013)

    Article  Google Scholar 

  2. Bo, X., Gao, W.-J.: Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms. Springer (2014)

    Google Scholar 

  3. Balas, E., Ho, A.: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In: Padberg, M.W. (ed.) Combinatorial Optimization. Mathematical Programming Studies, vol. 12, pp. 37–60. Elsevier North-Holland, The Netherlands (1980)

    Chapter  Google Scholar 

  4. Beasley, J., Chu, P.: A genetic algorithm for the set covering problem. European Journal of Operational Research 94(2), 392–404 (1996)

    Article  MATH  Google Scholar 

  5. Beasley, J.E.: An algorithm for set covering problem. European Journal of Operational Research 31(1), 85–93 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  6. Beasley, J.E.: A lagrangian heuristic for set-covering problems. Naval Research Logistics (NRL) 37(1), 151–164 (1990)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  8. Caprara, A., Fischetti, M., Toth, P., Vigo, D., Guida, P.L.: Algorithms for railway crew management. Math. Program. 79(1–3), 125–141 (1997)

    MATH  MathSciNet  Google Scholar 

  9. Caserta, M.: Tabu search-based metaheuristic algorithm for large-scale set covering problems. In: Doerner, K., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R., Reimann, M. (eds.) Metaheuristics. Operations Research/Computer Science Interfaces Series, vol. 39, pp. 43–63. Springer, US (2007)

    Chapter  Google Scholar 

  10. Crawford, B., Soto, R., Cuesta, R., Paredes, F.: Application of the artificial bee colony algorithm for solving the set covering problem. The Scientific World Journal (2014)

    Google Scholar 

  11. Crawford, B., Soto, R., Monfroy, E., Palma, W., Castro, C., Paredes, F.: Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Systems with Applications 40(5), 1690–1695 (2013)

    Article  Google Scholar 

  12. Crawford, B., Soto, R., Olivares-Surez, M., Paredes, F.: A binary firefly algorithm for the set covering problem. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Silhavy, P., Prokopova, Z., (eds.) Modern Trends and Techniques in Computer Science. Advances in Intelligent Systems and Computing, vol. 285, pp. 65–73. Springer International Publishing (2014)

    Google Scholar 

  13. Fisher, M.L., Rosenwein, M.B.: An interactive optimization system for bulk-cargo ship scheduling. Naval Research Logistics (NRL) 36(1), 27–42 (1989)

    Article  Google Scholar 

  14. Foster, B.A., Ryan, D.: An integer programming approach to the vehicle scheduling problem. Operations Research 27, 367–384 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  15. Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)

    Google Scholar 

  16. Goldberg, D.E.: Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems 5, 139–167 (1990)

    Google Scholar 

  17. Han, L., Kendall, G., Cowling, P.: An adaptive length chromosome hyperheuristic genetic algorithm for a trainer scheduling problem. In: Proceedings of the Fourth Asia-Pacific Conference on Simulated Evolution And Learning, (SEAL 2002), Orchid Country Club, Singapore, pp. 267–271 (2002)

    Google Scholar 

  18. Michalewicz, Z.: Genetic algorithms + data structures = evolution programs, 3rd edn. Springer-Verlag, London (1996)

    Book  MATH  Google Scholar 

  19. Mirjalili, S., Lewis, A.: S-shaped versus v-shaped transfer functions for binary particle swarm optimization. Swarm and Evolutionary Computation 9(0), 1–14 (2013)

    Article  Google Scholar 

  20. Rao, R.V., Patel, V.: An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems. International Journal of Industrial Engineering Computations 3, 535–560 (2012)

    Article  Google Scholar 

  21. Rao, R.V., Patel, V.: An improved teaching-learning-based optimization algorithm for solving unconstrained optimization problems. Scientia Iranica 20(3), 710–720 (2013)

    MathSciNet  Google Scholar 

  22. Rao, R.V., Patel, V.: Multi-objective optimization of heat exchangers using a modified teaching-learning-based optimization algorithm. Applied Mathematical Modelling 37, 1147–1162 (2013)

    Article  MathSciNet  Google Scholar 

  23. Rao, R.V., Patel, V.: Multi-objective optimization of two stage thermoelectric cooler using a modified teaching-learning-based optimization algorithm. Engineering Applications of Artificial Intelligence 26, 430–445 (2013)

    Article  Google Scholar 

  24. Rao, R.V., Savsani, V.J., Vakharia, D.P.: Teaching-learning-based optimization: A novel method for constrained mechanical design optimization problems. Computer-Aided Design 43, 303–315 (2011)

    Article  Google Scholar 

  25. Rao, R.V., Savsani, V.J.: Mechanical design optimization using advanced optimization techniques. Springer (2012)

    Google Scholar 

  26. Satapathy, S., Naik, A., Parvathi, K.: A teaching learning based optimization based on orthogonal design for solving global optimization problems. SpringerPlus 2(1), 130 (2013)

    Article  Google Scholar 

  27. Smith, B.M.: Impacs - a bus crew scheduling system using integer programming. Math. Program. 42(1), 181–187 (1988)

    Article  Google Scholar 

  28. Thomson, G.: A Simulated Annealing Heuristic for Shift-Scheduling Using Non-Continuously Available Employees. Computers and Operations Research 23, 275–288 (1996)

    Article  Google Scholar 

  29. Toregas, C., Swain, R., ReVelle, C., Bergman, L.: The location of emergency service facilities. Operations Research 19(6), 1363–1373 (1971)

    Article  MATH  Google Scholar 

  30. Vasko, F.J., Wolf, F.E., Stott, K.L.: A set covering approach to metallurgical grade assignment. European Journal of Operational Research 38(1), 27–34 (1989)

    Article  MathSciNet  Google Scholar 

  31. Zhang, Y., Wu, L., Wang, S., Huo, Y.: Chaotic artificial bee colony used for cluster analysis. In: Chen, R. (ed.) ICICIS 2011 Part I. CCIS, vol. 134, pp. 205–211. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile

    Broderick Crawford, Ricardo Soto, Felipe Aballay & Franklin Johnson

  2. Universidad San Sebastián, Santiago, Chile

    Broderick Crawford

  3. Universidad Central de Chile, Santiago, Chile

    Broderick Crawford

  4. Universidad Autónoma de Chile, Santiago, Chile

    Ricardo Soto

  5. Universidad Cientifica del Sur, Lima, Perú

    Ricardo Soto

  6. Covenant University, Ota, Nigeria

    Sanjay Misra

  7. Universidad de Playa Ancha, Valparaíso, Chile

    Franklin Johnson

  8. Escuela de Ingeniería Industrial, Universidad Diego Portales, Santiago, Chile

    Fernando Paredes

Authors
  1. Broderick Crawford
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ricardo Soto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Felipe Aballay
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sanjay Misra
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Franklin Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Fernando Paredes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Broderick Crawford .

Editor information

Editors and Affiliations

  1. University of Perugia, Perugia, Italy

    Osvaldo Gervasi

  2. University of Basilicata, Potenza, Italy

    Beniamino Murgante

  3. Covenant University, Canaanland, Nigeria

    Sanjay Misra

  4. University of Calgary, Calgary, Alberta, Canada

    Marina L. Gavrilova

  5. University of Minho, Braga, Portugal

    Ana Maria Alves Coutinho Rocha

  6. Polytechnic University, Bari, Italy

    Carmelo Torre

  7. Monash University, Clayton, Victoria, Australia

    David Taniar

  8. Kyushu Sangyo University, Fukuoka, Japan

    Bernady O. Apduhan

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Crawford, B., Soto, R., Aballay, F., Misra, S., Johnson, F., Paredes, F. (2015). A Teaching-Learning-Based Optimization Algorithm for Solving Set Covering Problems. In: Gervasi, O., et al. Computational Science and Its Applications -- ICCSA 2015. ICCSA 2015. Lecture Notes in Computer Science(), vol 9158. Springer, Cham. https://doi.org/10.1007/978-3-319-21410-8_33

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-21410-8_33

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-21409-2

  • Online ISBN: 978-3-319-21410-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation