A Literature Review on Combining Heuristics and Exact Algorithms in Combinatorial Optimization



Abstract Views
671

Downloads
597

Citations

Share

##plugins.themes.bootstrap3.article.sidebar##

Submitted Feb 10, 2022
Published Apr 29, 2022
10.24018/compute.2022.2.2.50

Abstract viewed = 671 times

Table of Contents

##plugins.themes.bootstrap3.article.main##

There are several approaches for solving hard optimization problems. Mathematical programming techniques such as (integer) linear programming-based methods and metaheuristic approaches are two extremely effective streams for combinatorial problems. Different research streams, more or less in isolation from one another, created these two. Only several years ago, many scholars noticed the advantages and enormous potential of building hybrids of combining mathematical programming methodologies and metaheuristics. In reality, many problems can be solved much better by exploiting synergies between these approaches than by “pure” classical algorithms. The key question is how to integrate mathematical programming methods and metaheuristics to achieve such benefits. This paper reviews existing techniques for such combinations and provides examples of using them for vehicle routing problems.

Keywords: Metaheuristics, pptimization-based heuristics, survey, VRP

References

  1. Garey MR, Johnson DS. Computers and Intractability, San Francisco. CA: W. H. Freeman. 1979.
     Google Scholar
  2. Hoos HH, Stützle T. Stochastic local search: Foundations and applications. Elsevier; 2004.
     Google Scholar
  3. Nemhauser GL, Savelsbergh MW, Sigismondi GC. MINTO, a mixed INTeger optimizer. Operations Research Letters. 1994; 15(1) :47-58.
     Google Scholar
  4. Oki E. Linear programming and algorithms for communication networks: a practical guide to network design, control, and management. CRC Press; 2012.
     Google Scholar
  5. Subhaa R, Jawahar N. ILOG CPLEX OPL modelling for machine cell formation. Int J Eng Tech. 2013; 5: 3734-41.
     Google Scholar
  6. Laundy R, Perregaard M, Tavares G, Tipi H, Vazacopoulos A. Solving hard mixed-integer programming problems with Xpress-MP: A MIPLIB 2003 case study. INFORMS Journal on Computing. 2009; 21(2): 304-13.
     Google Scholar
  7. Toth P, Vigo D, editors. The vehicle routing problem. Society for Industrial and Applied Mathematics; 2002.
     Google Scholar
  8. Glover FW, Kochenberger GA, editors. Handbook of metaheuristics. Springer Science & Business Media; 2006.
     Google Scholar
  9. Michel L, See A, Hentenryck PV. Distributed constraint-based local search. In International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg. 2006.
     Google Scholar
  10. Dantzig GB. Linear Programming and Extensions. Princeton, New Jersey: Princeton Univ. Press. 1963.
     Google Scholar
  11. Wolsey LA, Nemhauser GL. Integer and combinatorial optimization. John Wiley & Sons; 1999.
     Google Scholar
  12. Kirkpatrick S, Gelatt Jr CD, Vecchi MP. Optimization by simulated annealing. Science. 1983; 220(4598): 671-80.
     Google Scholar
  13. Glover F, Laguna M. Tabu search. In Handbook of combinatorial optimization. Springer, Boston, MA. 1998.
     Google Scholar
  14. Lourenço HR, Martin OC, Stützle T. Iterated local search. In Handbook of metaheuristics. Springer, Boston, MA. 2003.
     Google Scholar
  15. Hansen P, Mladenović N. An introduction to variable neighborhood search. In Meta-heuristics. Springer, Boston, MA. 1999.
     Google Scholar
  16. Bäck T, Fogel DB, Michalewicz Z. Handbook of evolutionary computation. Release. 1997; 97(1): B1.
     Google Scholar
  17. Glover F, Laguna M, Martí R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000; 29(3): 653-84.
     Google Scholar
  18. Moscato P, Cotta C. A gentle introduction to memetic algorithms. In Handbook of metaheuristics. Springer, Boston, MA. 2003.
     Google Scholar
  19. Larrañaga P, Lozano JA, editors. Estimation of distribution algorithms: A new tool for evolutionary computation. Springer Science & Business Media; 2001.
     Google Scholar
  20. Puchinger J, Raidl GR. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In International work-conference on the interplay between natural and artificial computation. Springer, Berlin, Heidelberg. 2005.
     Google Scholar
  21. Danna E, Pape CL. Two generic schemes for efficient and robust cooperative algorithms. In Constraint and Integer Programming. Springer, Boston, MA. 2004.
     Google Scholar
  22. Ball MO. Heuristics based on mathematical programming. Surveys in Operations Research and Management Science. 2011; 16(1): 21-38.
     Google Scholar
  23. Doerner KF, Schmid V. Survey: matheuristics for rich vehicle routing problems. In International Workshop on Hybrid Metaheuristic. Berlin, Heidelberg. 2010.
     Google Scholar
  24. Fischetti M, Lodi A. Repairing MIP infeasibility through local branching. Computers & Operations Research. 2008; 35(5): 1436-45.
     Google Scholar
  25. Archetti C, Speranza MG. A survey on matheuristics for routing problems. EURO Journal on Computational Optimization. 2014; 2(4): 223-46.
     Google Scholar
  26. Bazaraa MS, Jarvis JJ, Sherali HD. Linear programming and network flows. John Wiley & Sons; 2008.
     Google Scholar
  27. Fakhravar H. Fuzzy inventory model with receiving reparative order and considering imperfect quality items. 2020.
     Google Scholar
  28. Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Operations research. 1999; 47(5): 730-43.
     Google Scholar
  29. Ceria S, Nobili P, Sassano A. A Lagrangian-based heuristic for large-scale set covering problems. Mathematical Programming. 1998; 81(2): 215-28.
     Google Scholar
  30. Atamtürk A, Nemhauser GL, Savelsbergh MW. A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems. Journal of Heuristics. 1996; 1(2): 247-59.
     Google Scholar
  31. Tahami H, Mirzazadeh A, Arshadi-khamseh A, Gholami-Qadikolaei A. A periodic review integrated inventory model for buyer’s unidentified protection interval demand distribution. Cogent Engineering. 2016; 3(1): 1206689.
     Google Scholar
  32. Boschetti MA, Mingozzi A, Ricciardelli S. A dual ascent procedure for the set partitioning problem. Discrete Optimization. 2008; 5(4): 735-47.
     Google Scholar
  33. Van Krieken MG, Fleuren H, Peeters R. A Lagrangean relaxation based algorithm for solving set partitioning problems. 2005.
     Google Scholar
  34. Boschetti MA, Mingozzi A, Ricciardelli S. An exact algorithm for the simplified multiple depot crew scheduling problem. Annals of Operations Research. 2004; 127(1): 177-201.
     Google Scholar
  35. Tahami H, Fakhravar H. A fuzzy inventory model considering imperfect quality items with receiving reparative batch and order. European Journal of Engineering and Technology Research. 2020; 5(10): 1179-85.
     Google Scholar
  36. Freling R, Huisman D, Wagelmans AP. Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling. 2003; 6(1): 63-85.
     Google Scholar
  37. Hoffman KL, Padberg M. Solving airline crew scheduling problems by branch-and-cut. Management Science. 1993; 39(6): 657-82.
     Google Scholar
  38. Mingozzi A, Boschetti MA, Ricciardelli S, Bianco L. A set partitioning approach to the crew scheduling problem. Operations Research. 1999; 47(6): 873-88.
     Google Scholar
  39. Tahami H, Fakhravar H. Multilevel Reorder Strategy-based Supply Chain Model. In5th North American Conference on Industrial Engineering and Operations Management (IEOM), Michigan, USA 2020.
     Google Scholar
  40. Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks. 1981; 11(2): 109-24.
     Google Scholar
  41. Koskosidis YA, Powell WB, Solomon MM. An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints. Transportation science. 1992; 26(2): 69-85.
     Google Scholar
  42. Fakhravar, H, Tahami, H. Systems statistical engineering-hierarchical fuzzy constraint propagation. 2021.
     Google Scholar
  43. Bramel J, Simchi-Levi D. A location based heuristic for general routing problems. Operations research. 1995; 43(4): 649-60.
     Google Scholar
  44. Fakhravar H, Tahami H. International Co-Branding and Firms Finance Performance. arXiv preprint arXiv:2202.07128. 2022 Feb 15.
     Google Scholar
  45. Bramel J, Simchi-Levi D. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Operations Research. 1996; 44(3): 501-9.
     Google Scholar
  46. Fakhravar H. Quantifying uncertainty in risk assessment using fuzzy theory. arXiv preprint arXiv:2009.09334. 2020 Sep 20.
     Google Scholar
  47. Fakhravar H. Application of Failure Modes and Effects Analysis in the Engineering Design. 2021.
     Google Scholar
  48. Dumitrescu I, Stützle T. Usage of exact algorithms to enhance stochastic local search algorithms. In Matheuristics. Springer, Boston, MA. 2009.
     Google Scholar
  49. Ouabira MM, Fakhravar H. Effective Project Management and the Role of Quality Assurance throughout the Project Life Cycle. European Journal of Engineering and Technology Research. 2021; 6(5).
     Google Scholar
  50. Ahuja RK, Ergun Ö, Orlin JB, Punnen AP. A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics. 2002; 123(1-3): 75-102.
     Google Scholar
  51. Sniedovich M, Viß S. The corridor method: a dynamic programming inspired metaheuristic. Control and Cybernetics. 2006; 35(3): 551-78.
     Google Scholar
  52. Congram RK, Potts CN, van de Velde SL. An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing. 2002; 14(1): 52-67.
     Google Scholar
  53. Bartolini E, Mingozzi A. Algorithms for the non-bifurcated network design problem. Journal of Heuristics. 2009; 15(3): 259-81
     Google Scholar
  54. Yahoodik S, Tahami H, Unverricht J, Yamani Y, Handley H, Thompson D. Blink Rate as a Measure of Driver Workload during Simulated Driving. In Proceedings of the Human Factors and Ergonomics Society Annual Meeting. Sage CA: Los Angeles, CA: SAGE Publications. 2020.
     Google Scholar
  55. Woodruff DL. A chunking based selection strategy for integrating meta-heuristics with branch and bound. In Meta-Heuristics. Springer, Boston, MA. 1999.
     Google Scholar
  56. Fakhravar H. Application of Failure Modes and Effects Analysis in the Engineering Design Process. arXiv preprint arXiv:2101.05444. 2021 Jan 14.
     Google Scholar
  57. Tahami H, Fakhravar H. A fuzzy inventory model considering imperfect quality items with receiving reparative batch and order overlapping. arXiv preprint arXiv:2009.05881. 2020 Sep 12.
     Google Scholar
  58. Woodruff DL. A chunking based selection strategy for integrating meta-heuristics with branch and bound. In Meta-Heuristics. Springer, Boston, MA. 1999.
     Google Scholar
  59. Plateau A, Tachat D, Tolla P. A hybrid search combining interior point methods and metaheuristics for 0–1 programming. International Transactions in Operational Research. 2002; 9(6): 731-46.
     Google Scholar
  60. Raidl GR. An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. In1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No. 98TH8360) 1998 May 4 (pp. 207-211). IEEE.
     Google Scholar
  61. Vasquez M, Hao JK. A hybrid approach for the 0-1 multidimensional knapsack problem. IJCAI. 2001.
     Google Scholar
  62. Vasquez M, Vimont Y. Improved results on the 0–1 multidimensional knapsack problem. European Journal of Operational Research. 2005; 165(1): 70-81.
     Google Scholar
  63. Tahami H, Mirzazadeh A, Gholami-Qadikolaei A. Simultaneous control on lead time elements and ordering cost for an inflationary inventory-production model with mixture of normal distributions LTD under finite capacity. RAIRO-Operations Research. 2019; 53(4): 1357-84.
     Google Scholar
  64. Bramel J, Simchi-Levi D. A location based heuristic for general routing problems. Operations Research. 1995; 43(4): 649-660.
     Google Scholar
  65. Fakhravar H. Combining heuristics and Exact Algorithms: A Review. arXiv preprint arXiv:2202.02799. 2022 Feb 6.
     Google Scholar
  66. Fakhravar H. Quantifying uncertainty in risk assessment using fuzzy theory. arXiv preprint arXiv:2009.09334. 2020 Sep 20.
     Google Scholar
  67. Natarajan G, Ng EH, Katina PF. Systems statistical engineering-hierarchical fuzzy constraint propagation. 2021.
     Google Scholar