[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Less Is More Approach in Heuristic Optimization

  • Chapter
  • First Online:
The Palgrave Handbook of Operations Research

Abstract

Generally speaking, the phrase “Less is more” implies that we use as few resources as possible in doing something while providing the best possible outcome. This approach has been applied successfully in almost all the scientific and art disciplines. The idea has also been recently explored with success in solving hard optimization problems. In this chapter, we first give the main principles of the less is more approach (LIMA) in solving continuous and combinatorial Global Optimization problems, and then explain in more detail some of its successful implementations.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 159.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 199.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 199.99
Price includes VAT (United Kingdom)
  • Durable hardcover 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

Similar content being viewed by others

References

  1. Amirgaliyeva, Z., Mladenović, N., Todosijević, R., and Urošević, D. (2017) Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, 260(2):444–459.

    Article  Google Scholar 

  2. Aurenhammer, F., Klein, R., and Lee, D.-T. (2013). Voronoi Diagrams and Delaunay Triangulations. World Scientific, New Jersey.

    Google Scholar 

  3. Austin, C. M. (1974). The evaluation of urban public facility location: An alternative to benefit-cost analysis. Geographical Analysis, 6:135–145.

    Article  Google Scholar 

  4. Austin, C. M., Smith, T. E., and Wolpert, J. (1970). The implementation of controversial facility-complex programs. Geographical Analysis, 2:315–329.

    Article  Google Scholar 

  5. Bannard, O. M. and Cyster, J. G. (2012). When less signaling is more. Science, 336:1120–1121.

    Article  Google Scholar 

  6. Bassiri-Gharb, N. (2020). Less can be more in functional materials. Science, 369:252–253.

    Article  Google Scholar 

  7. Bornholdt, S. (2005). Less is more in modeling large genetic networks. Science, 310:449–451.

    Article  Google Scholar 

  8. Brimberg, J. and Drezner, Z. (2013). A new heuristic for solving the \(p\)-median problem in the plane. Computers & Operations Research, 40:427–437.

    Article  Google Scholar 

  9. Brimberg, J. and Drezner, Z. (2021). Improved starting solutions for the planar \(p\)-median problem. Yugoslav Journal of Operations Research, 31:45–64.

    Article  Google Scholar 

  10. Brimberg, J., Drezner, Z., Mladenović, N., and Salhi, S. (2014). A new local search for continuous location problems. European Journal of Operational Research, 232:256–265.

    Article  Google Scholar 

  11. Brimberg, J., Hansen, P., Mladenović, N., and Taillard, E. (2000). Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Operations Research, 48:444–460.

    Article  Google Scholar 

  12. Brimberg, J., Hansen, P., Mladonovic, N., and Salhi, S. (2008). A survey of solution methods for the continuous location allocation problem. International Journal of Operations Research, 5:1–12.

    Google Scholar 

  13. Brimberg, J. and Hodgson, M. J. (2011). Heuristics for location models. In Eiselt, H. A. and Marianov, V., editors, Foundations of Location Analysis: International Series in Operations Research & Management Science, Vol. 155, pages 335–355. Springer, New York, NY.

    Chapter  Google Scholar 

  14. Brimberg, J., Janićijević, S., Mladenović, N., and Urošević, D. (2017). Solving the clique partitioning problem as a maximally diverse grouping problem. Optimization Letters, 11(6):1123–1135

    Article  Google Scholar 

  15. Brimberg, J., Mladenović, N., Todosijević, R., and Urošević, D. (2017). Less is more: solving the max-mean diversity problem with variable neighborhood search. Information Sciences, 382:179–200.

    Article  Google Scholar 

  16. Brimberg, J., Mladenović, N., and Urošević, D. (2016). Solving the maximally diverse grouping problem by skewed general variable neighborhood search. Information Sciences, 295:650–675.

    Article  Google Scholar 

  17. Brimberg, J., Mladenović, N., Todosijević, R., and Urošević, D. (2019). Solving the capacitated clustering problem with variable neighborhood search. Annals of Operations Research, 272 (1-2):289–321.

    Article  Google Scholar 

  18. Burkard, R. E., Karisch, S. E., and Rendl, F. (1997). Qaplib–a quadratic assignment problem library. Journal of Global optimization, 10:391–403. https://www.opt.math.tugraz.at/qaplib/.

    Google Scholar 

  19. Chong, L.D. (2011). Exosomes Deliver. Science, 332:515.

    Article  Google Scholar 

  20. Church, R. L. (2019). Understanding the Weber location paradigm. In Eiselt, H. A. and Marianov, V., editors, Contributions to Location Analysis - In Honor of Zvi Drezner’s 75th Birthday, pages 69–88. Springer Nature, Switzerland.

    Chapter  Google Scholar 

  21. Church, R. L., and Drezner, Z. (2022). Extensions to the weber problem. Computers and Operations Research, 138:105468.

    Book  Google Scholar 

  22. Church, R. L. and Garfinkel, R. S. (1978). Locating an obnoxious facility on a network. Transportation Science, 12:107–118.

    Article  Google Scholar 

  23. Cooper, L. (1963). Location-allocation problems. Operations Research, 11:331–343.

    Article  Google Scholar 

  24. Cooper, L. (1964). Heuristic methods for location-allocation problems. SIAM Review, 6:37–53.

    Article  Google Scholar 

  25. Costa, L. R., Aloise, D., and Mladenović, N. (2017). Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering. Information Sciences, 415:247–253.

    Article  Google Scholar 

  26. CPLEX, IBM ILOG (2019). 12.10: User’s Manual for CPLEX. International Business Machines Corporation, Incline Village, NV.

    Google Scholar 

  27. Daskin, M. S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. John Wiley & Sons, New York.

    Book  Google Scholar 

  28. Daskin, M. S. and Maass, K. L. (2015). The p-median problem. In Laporte, G., Nickel, S., and da Gama, F. S., editors, Location science, pages 21–45. Springer.

    Google Scholar 

  29. Drezner, T., Drezner, Z., and Kalczynski, P. (2020). Multiple obnoxious facilities location: A cooperative model. IISE Transactions, 52:1403–1412.

    Article  Google Scholar 

  30. Drezner, Z. (2006). Finding a cluster of points and the grey pattern quadratic assignment problem. OR Spectrum, 28:417–436.

    Article  Google Scholar 

  31. Drezner, Z. (2015). The quadratic assignment problem. In Laporte, G., Nickel, S., and da Gama, F. S., editors, Location Science, pages 345–363. Springer, Chum, Heidelberg.

    Google Scholar 

  32. Drezner, Z., Brimberg, J., Salhi, S., and Mladenović, N. (2016). New local searches for solving the multi-source Weber problem. Annals of Operations Research, 246:181–203.

    Article  Google Scholar 

  33. Drezner, Z., Hahn, P. M., and Taillard, É. D. (2005). Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Annals of Operations Research, 139:65–94.

    Article  Google Scholar 

  34. Drezner, Z. and Kalczynski, P. (2020). Solving non-convex non-linear programs with reverse convex constraints by sequential linear programming. International Transactions in Operational Research, 27:1320–1342.

    Article  Google Scholar 

  35. Drezner, Z., Kalczynski, P., Misevicius, A., and G. Palubeckis. (2022). Finding optimal solutions to Several gray pattern instances. Optimization Letters, 16:713–722.

    Article  Google Scholar 

  36. Drezner, Z., Kalczynski, P., and Salhi, S. (2019). The multiple obnoxious facilities location problem on the plane: A Voronoi based heuristic. OMEGA: The International Journal of Management Science, 87:105–116.

    Google Scholar 

  37. Drezner, Z., Klamroth, K., Schöbel, A., and Wesolowsky, G. O. (2002). The Weber problem. In Drezner, Z. and Hamacher, H. W., editors, Facility Location: Applications and Theory, pages 1–36. Springer, Berlin.

    Chapter  Google Scholar 

  38. Drezner, Z., Misevičius, A., and Palubeckis, G. (2015). Exact algorithms for the solution of the grey pattern quadratic assignment problem. Mathematical Methods of Operations Research, 82:85–105.

    Article  Google Scholar 

  39. Drezner, Z. and Salhi, S. (2017). Incorporating neighborhood reduction for the solution of the planar \(p\)-median problem. Annals of Operations Research, 258:639–654.

    Article  Google Scholar 

  40. Duarte, A., Laguna, M., Martí, R., and Sánchez-Oro, J. (2014). Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem. Computers & operations research, 51:123–129.

    Article  Google Scholar 

  41. Duarte, A., Sánchez-Oro, J., Resende, M. G., Glover, F., and Martí, R. (2015). Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization. Information Sciences, 296:46–60.

    Article  Google Scholar 

  42. Galinier, P., Boujbel, Z., and Fernandes, M. C. (2011). An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 191:1–22.

    Article  Google Scholar 

  43. Gill, P. E., Murray, W., and Saunders, M. A. (2005). SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Review, 47:99–131.

    Article  Google Scholar 

  44. Glover, F., and Laguna, M. (1998). Tabu Search. Kluwer Academic Publishers, Boston/Dordrecht/London.

    Google Scholar 

  45. Glover, F., Ye, T., Punnen, A. P., and Kochenberger, G. (2015). Integrating tabu search and vlsn search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs. European Journal of Operational Research, 241:697–707.

    Article  Google Scholar 

  46. Gonçalves Silva, K., Aloise, D., Xavier-De-Souza, S., Mladenović, N. (2018). Less is more: simplified Nelder-Mead method for large unconstrained optimization. Yugoslav Journal of Operations Research, 28:153–169.

    Google Scholar 

  47. Gurobi Optimization Incorporated (2018). Gurobi optimizer reference manual. URL http://www. gurobi. com.

    Google Scholar 

  48. Hahn, P. M., Zhu, Y.-R., Guignard, M., Hightower, W. L., and Saltzman, M. J. (2012). A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS Journal on Computing, 24:202–209.

    Article  Google Scholar 

  49. Hansen, P. and Mladenović, N. (1997). Variable neighborhood search. Computers and operations research, 24(11):1097–1101.

    Article  Google Scholar 

  50. Hansen, P., Mladenović, N., and Taillard, É. (1998). Heuristic solution of the multisource Weber problem as a \(p\)-median problem. Operations Research Letters, 22:55–62.

    Article  Google Scholar 

  51. Hosseini, S. and Esfahani, A. M. (2009). Obnoxious facility location. In Facility Location, pages 315–345. Springer.

    Google Scholar 

  52. Kaiser, J. (2017). When less is more. Science, 355:1144–1146.

    Article  Google Scholar 

  53. Kalczynski, P., Brimberg, J., and Z, Drezner. (2022). Less is more: Discrete starting solutions in the planar p-median problem. TOP, 30:34–59.

    Article  Google Scholar 

  54. Kalczynski, P. and Drezner, Z. (2019). Locating multiple facilities using the max-sum objective. Computers and Industrial Engineering, 129:136–143.

    Article  Google Scholar 

  55. Kalczynski, P., and Z, Drezner. (2022). Extremely non-convex optimization problems: The case of the multiple obnoxious facilities location. Optimization Letters, 16:1153–1166.

    Article  Google Scholar 

  56. Kalczynski, P. and Drezner, Z. (2021b). The obnoxious facilities planar \(p\)-median problem. OR Spectrum, 43:577–593.

    Article  Google Scholar 

  57. Kalczynski P., Suzuki, A., and Z. Drezner. (2022). Multiple obnoxious facilities with weighted demand points. Journal of the Operational Research Society, 73:598–607.

    Article  Google Scholar 

  58. Kang, H. R. (1999). Digital color halftoning. SPIE press.

    Google Scholar 

  59. Karapetyan, D., Punnen, A. P., and Parkes, A. J. (2017). Markov chain methods for the bipartite boolean quadratic programming problem. European Journal of Operational Research, 260:494–506.

    Article  Google Scholar 

  60. Kuenne, R. E. and Soland, R. M. (1972). Exact and approximate solutions to the multisource Weber problem. Mathematical Programming, 3:193–209.

    Article  Google Scholar 

  61. Kuo, C.-C., Glover, F., and Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sciences, 24:1171–1185.

    Article  Google Scholar 

  62. van Laarhoven, P. J. M., Aarts, E. H. L. (1987). Simulated annealing. In: Simulated Annealing: Theory and Applications. Mathematics and Its Applications, vol 37, pages 7–15, Springer, Dordrecht.

    Google Scholar 

  63. Lau, D. L. and Arce, G. R. (2018). Modern digital halftoning. CRC Press.

    Book  Google Scholar 

  64. Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., and Querido, T. (2007). A survey for the quadratic assignment problem. European Journal of Operational Research, 176:657–690.

    Article  Google Scholar 

  65. Love, R. F., Morris, J. G., and Wesolowsky, G. O. (1988). Facilities Location: Models & Methods. North Holland, New York, NY.

    Google Scholar 

  66. Lu, S., Pei, J., Liu, X., Qian, X., Mladenovic, N., and Pardalos, P. M. (2020). Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing. Journal of Scheduling, 23:649–664.

    Article  Google Scholar 

  67. McCartney, M. (2011). Calendar effects. Science, 334:1324–1324.

    Article  Google Scholar 

  68. Megiddo, N. and Supowit, K. (1984). On the complexity of some common geometric location problems. SIAM Journal on Computing, 18:182–196.

    Article  Google Scholar 

  69. Melachrinoudis, E. (2011). The location of undesirable facilities. In Foundations of location analysis, pages 207–239. Springer, New York.

    Chapter  Google Scholar 

  70. Mikić, M., Todosijević, R., Urošević, D. (2019). Less is more: General variable neighborhood search for the capacitated modular hub location problem. Computers and Operations Research, 110:101–115.

    Article  Google Scholar 

  71. Misevicius, A., Palubeckis, G., and Drezner, Z. (2021). Hierarchicity-based (self-similar) hybrid genetic algorithm for the grey pattern quadratic assignment problem. Memetic Computing, 13:69–90. https://doi.org/10.1007/s12293-020-00321-6.

    Article  Google Scholar 

  72. Mladenovi?, N., Alkandari, A., Pei, J., Todosijevi?, R., and Pardalos, P. M. (2020). Less is more approach: basic variable neighborhood search for the obnoxious p-median problem. International Transactions in Operational Research, 27:480–493.

    Google Scholar 

  73. Mladenović, N., Todosijević, R., and Urošević, D. (2013). An efficient general variable neighborhood search for large travelling salesman problem with time windows. Yugoslav Journal of Operations Research, 23(1):19–30.

    Article  Google Scholar 

  74. Mladenović, N., Todosijević, R., and Urošević, D. (2016). Less is more: basic variable neighborhood search for minimum differential dispersion problem. Information Sciences, 326:160–171.

    Article  Google Scholar 

  75. Mladenović, N., Urošević, D., aand Pérez-Brito, D. (2016). Variable neighborhood search for minimum arrangement problem. Yugoslav Journal of Operations Research, 26(1):3–16.

    Google Scholar 

  76. Mumphrey, A. J. and Wolpert, J. (1973). Equity considerations and concessions in the siting of public facilities. Economic Geography, 49:109–121.

    Article  Google Scholar 

  77. Nelder, J. A. and Mead, R. (1965). A simplex method for function minimization. Computer Journal, 7:308–313.

    Article  Google Scholar 

  78. Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. (2000). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley Series in Probability and Statistics. John Wiley, Hoboken, NJ.

    Book  Google Scholar 

  79. Pei, J., Dražić, Z., Dražić, M., Mladenović, N., and Pardalos, P. M. (2019). Continuous variable neighborhood search (c-vns) for solving systems of nonlinear equations. INFORMS Journal on Computing, 31:235–250.

    Article  Google Scholar 

  80. Pei, J., Mladenović, N., Urošević, D., Brimberg, J., and Liu, X. (2020). Solving the traveling repairman problem with profits: A novel variable neighborhood search approach. Information Sciences, 507:108–123.

    Article  Google Scholar 

  81. Plastria, F. and Carrizosa, E. (1999). Undesirable facility location in the Euclidean plane with minimal covering objectives. European Journal of Operational Research, 119:158–180.

    Article  Google Scholar 

  82. Prokopyev, O., Kong, N., and Martinez-Torres, D. (2009). The equitable dispersion problem. European Journal of Operational Research, 197:59–67.

    Article  Google Scholar 

  83. Ratli, M., Urošević, D., El Cadi, A.A., Brimberg, J., Mladenović, N., and Todosijević, R. (2020). An efficient heuristic for a hub location routing problem. Optimization Letters, DOI: https://doi.org/10.1007/s11590-020-01675-z,

    Article  Google Scholar 

  84. Reinelt, G. (1991). TSLIB a traveling salesman library. ORSA Journal on Computing, 3:376–384.

    Article  Google Scholar 

  85. ReVelle, C. S. and Swain, R. W. (1970). Central facilities location. Geographical analysis, 2:30–42.

    Article  Google Scholar 

  86. Shamos, M. and Hoey, D. (1975). Closest-point problems. Proceedings 16th Annual Symposium on the Foundations of Computer Science, Berkeley, CA, pages 151–162.

    Google Scholar 

  87. Shi, L. Z. (2020). Less is more for adoptive immunotherapy? Science Translational Medicine, 12.

    Google Scholar 

  88. Sugihara, K. and Iri, M. (1992). Construction of the Voronoi diagram for “one million" generators in single-precision arithmetic. Proceedings of the IEEE, 80:1471–1484.

    Article  Google Scholar 

  89. Suzuki, A. and Okabe, A. (1995). Using Voronoi diagrams. In Drezner, Z., editor, Facility Location: A Survey of Applications and Methods, pages 103–118. Springer, New York.

    Chapter  Google Scholar 

  90. Taillard, É. D. (1995). Comparison of iterative searches for the quadratic assignment problem. Location Science, 3:87–105.

    Article  Google Scholar 

  91. Todosijević, R., Urošević, D., Mladenović, N., Hanafi, S. (2017). A general variable neighborhood search for solving the uncapacitated \(r\)-allocation \(p\)-hub median problem. Optimization Letters, 11(6):1109-1121.

    Article  Google Scholar 

  92. Ulichney, R. (1987). Digital halftoning. MIT press.

    Google Scholar 

  93. Urošević, D., Alghoul, Y. I. Y., Amirgaliyeva, Z., and Mladenović, N. (2019). Less is more: Tabu search for bipartite quadratic programming problem. In International Conference on Mathematical Optimization Theory and Operations Research, pages 390–401.

    Google Scholar 

  94. Voronoï, G. (1908). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik, 134:198–287.

    Article  Google Scholar 

  95. Weber, A. (1909). Über den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. English Translation: on the Location of Industries. University of Chicago Press, Chicago, IL. Translation published in 1929.

    Google Scholar 

  96. Wesolowsky, G. O. (1993). The Weber problem: History and perspectives. Location Science, 1:5–23.

    Google Scholar 

  97. Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing, 4:65–85.

    Article  Google Scholar 

  98. Wolfram, S. (2020). Mathematica, Version 12.2. Champaign, IL. https://www.wolfram.com/mathematica.

    Google Scholar 

Download references

Acknowledgements

The first author is partially supported by the Khalifa University of Science and Technology under Award No. RC2 DSO, and by the Committee of Science of the Ministry of Education and Science of the Republic of Kazakhstan under the grant number AP08856034. The work of the fourth author is partially supported by the Serbian Ministry of Education, Science and Technological Development through the Mathematical Institute of the Serbian Academy of Sciences and Arts.

Author information

Authors and Affiliations

  1. Industrial System Engineering, Khalifa University, Abu Dhabi, UAE

    Nenad Mladenović

  2. College of Business and Economics, California State University-Fullerton, Fullerton, CA, 92834, USA

    Zvi Drezner

  3. Royal Military College of Canada, Kingston, ON, Canada

    Jack Brimberg

  4. Mathematical Institute of the Serbian Academy of Sciences and Arts, Belgrade, Serbia

    Dragan Urošević

Authors
  1. Nenad Mladenović
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zvi Drezner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jack Brimberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dragan Urošević
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dragan Urošević .

Editor information

Editors and Affiliations

  1. Kent Business School, University of Kent, Canterbury, UK

    Saïd Salhi

  2. Lancaster University, Lancaster, UK

    John Boylan

Additional information

A Tribute to Professor Nenad Mladenovic

We sadly announce that Professor Nenad Mladenović passed away in May 2022, before the publication of this book was completed. His sudden death from a heart attack shocked his many friends and colleagues at universities and research institutes around the globe. Nenad introduced several important ideas in Operations Research. He is known principally for his pioneering work in Variable Neighborhood Search, which was later extended to Formulation Space Search (the topic of another chapter in this book). The VNS methodology has been applied with great success on many combinatorial and global optimization problems. It is interesting that while heuristic methods have tended to become more and more complex in order to obtain a competitive edge over other heuristics, Nenad has argued for the principle of simple designs. This is the less-is-more principal, which is the topic of this chapter. Simple heuristic designs are not only competitive; they also lead to a better understanding of the underlying nature of the problem.

The passing of Nenad is a great loss to the Operations Research community. His work has stopped, but it will continue to inspire us for many years to come. Rest in peace, my good friend.

Jack Brimberg.

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Mladenović, N., Drezner, Z., Brimberg, J., Urošević, D. (2022). Less Is More Approach in Heuristic Optimization. In: Salhi, S., Boylan, J. (eds) The Palgrave Handbook of Operations Research . Palgrave Macmillan, Cham. https://doi.org/10.1007/978-3-030-96935-6_14

Download citation

Publish with us

Policies and ethics

Search

Navigation