A Literature Review on Combining Heuristics and Exact Algorithms in Combinatorial Optimization
##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.
References
-
Garey MR, Johnson DS. Computers and Intractability, San Francisco. CA: W. H. Freeman. 1979.
Google Scholar
1
-
Hoos HH, Stützle T. Stochastic local search: Foundations and applications. Elsevier; 2004.
Google Scholar
2
-
Nemhauser GL, Savelsbergh MW, Sigismondi GC. MINTO, a mixed INTeger optimizer. Operations Research Letters. 1994; 15(1) :47-58.
Google Scholar
3
-
Oki E. Linear programming and algorithms for communication networks: a practical guide to network design, control, and management. CRC Press; 2012.
Google Scholar
4
-
Subhaa R, Jawahar N. ILOG CPLEX OPL modelling for machine cell formation. Int J Eng Tech. 2013; 5: 3734-41.
Google Scholar
5
-
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
6
-
Toth P, Vigo D, editors. The vehicle routing problem. Society for Industrial and Applied Mathematics; 2002.
Google Scholar
7
-
Glover FW, Kochenberger GA, editors. Handbook of metaheuristics. Springer Science & Business Media; 2006.
Google Scholar
8
-
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
9
-
Dantzig GB. Linear Programming and Extensions. Princeton, New Jersey: Princeton Univ. Press. 1963.
Google Scholar
10
-
Wolsey LA, Nemhauser GL. Integer and combinatorial optimization. John Wiley & Sons; 1999.
Google Scholar
11
-
Kirkpatrick S, Gelatt Jr CD, Vecchi MP. Optimization by simulated annealing. Science. 1983; 220(4598): 671-80.
Google Scholar
12
-
Glover F, Laguna M. Tabu search. In Handbook of combinatorial optimization. Springer, Boston, MA. 1998.
Google Scholar
13
-
Lourenço HR, Martin OC, Stützle T. Iterated local search. In Handbook of metaheuristics. Springer, Boston, MA. 2003.
Google Scholar
14
-
Hansen P, Mladenović N. An introduction to variable neighborhood search. In Meta-heuristics. Springer, Boston, MA. 1999.
Google Scholar
15
-
Bäck T, Fogel DB, Michalewicz Z. Handbook of evolutionary computation. Release. 1997; 97(1): B1.
Google Scholar
16
-
Glover F, Laguna M, Martí R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000; 29(3): 653-84.
Google Scholar
17
-
Moscato P, Cotta C. A gentle introduction to memetic algorithms. In Handbook of metaheuristics. Springer, Boston, MA. 2003.
Google Scholar
18
-
Larrañaga P, Lozano JA, editors. Estimation of distribution algorithms: A new tool for evolutionary computation. Springer Science & Business Media; 2001.
Google Scholar
19
-
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
20
-
Danna E, Pape CL. Two generic schemes for efficient and robust cooperative algorithms. In Constraint and Integer Programming. Springer, Boston, MA. 2004.
Google Scholar
21
-
Ball MO. Heuristics based on mathematical programming. Surveys in Operations Research and Management Science. 2011; 16(1): 21-38.
Google Scholar
22
-
Doerner KF, Schmid V. Survey: matheuristics for rich vehicle routing problems. In International Workshop on Hybrid Metaheuristic. Berlin, Heidelberg. 2010.
Google Scholar
23
-
Fischetti M, Lodi A. Repairing MIP infeasibility through local branching. Computers & Operations Research. 2008; 35(5): 1436-45.
Google Scholar
24
-
Archetti C, Speranza MG. A survey on matheuristics for routing problems. EURO Journal on Computational Optimization. 2014; 2(4): 223-46.
Google Scholar
25
-
Bazaraa MS, Jarvis JJ, Sherali HD. Linear programming and network flows. John Wiley & Sons; 2008.
Google Scholar
26
-
Fakhravar H. Fuzzy inventory model with receiving reparative order and considering imperfect quality items. 2020.
Google Scholar
27
-
Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Operations research. 1999; 47(5): 730-43.
Google Scholar
28
-
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
29
-
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
30
-
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
31
-
Boschetti MA, Mingozzi A, Ricciardelli S. A dual ascent procedure for the set partitioning problem. Discrete Optimization. 2008; 5(4): 735-47.
Google Scholar
32
-
Van Krieken MG, Fleuren H, Peeters R. A Lagrangean relaxation based algorithm for solving set partitioning problems. 2005.
Google Scholar
33
-
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
34
-
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
35
-
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
36
-
Hoffman KL, Padberg M. Solving airline crew scheduling problems by branch-and-cut. Management Science. 1993; 39(6): 657-82.
Google Scholar
37
-
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
38
-
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
39
-
Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks. 1981; 11(2): 109-24.
Google Scholar
40
-
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
41
-
Fakhravar, H, Tahami, H. Systems statistical engineering-hierarchical fuzzy constraint propagation. 2021.
Google Scholar
42
-
Bramel J, Simchi-Levi D. A location based heuristic for general routing problems. Operations research. 1995; 43(4): 649-60.
Google Scholar
43
-
Fakhravar H, Tahami H. International Co-Branding and Firms Finance Performance. arXiv preprint arXiv:2202.07128. 2022 Feb 15.
Google Scholar
44
-
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
45
-
Fakhravar H. Quantifying uncertainty in risk assessment using fuzzy theory. arXiv preprint arXiv:2009.09334. 2020 Sep 20.
Google Scholar
46
-
Fakhravar H. Application of Failure Modes and Effects Analysis in the Engineering Design. 2021.
Google Scholar
47
-
Dumitrescu I, Stützle T. Usage of exact algorithms to enhance stochastic local search algorithms. In Matheuristics. Springer, Boston, MA. 2009.
Google Scholar
48
-
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
49
-
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
50
-
Sniedovich M, Viß S. The corridor method: a dynamic programming inspired metaheuristic. Control and Cybernetics. 2006; 35(3): 551-78.
Google Scholar
51
-
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
52
-
Bartolini E, Mingozzi A. Algorithms for the non-bifurcated network design problem. Journal of Heuristics. 2009; 15(3): 259-81
Google Scholar
53
-
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
54
-
Woodruff DL. A chunking based selection strategy for integrating meta-heuristics with branch and bound. In Meta-Heuristics. Springer, Boston, MA. 1999.
Google Scholar
55
-
Fakhravar H. Application of Failure Modes and Effects Analysis in the Engineering Design Process. arXiv preprint arXiv:2101.05444. 2021 Jan 14.
Google Scholar
56
-
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
57
-
Woodruff DL. A chunking based selection strategy for integrating meta-heuristics with branch and bound. In Meta-Heuristics. Springer, Boston, MA. 1999.
Google Scholar
58
-
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
59
-
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
60
-
Vasquez M, Hao JK. A hybrid approach for the 0-1 multidimensional knapsack problem. IJCAI. 2001.
Google Scholar
61
-
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
62
-
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
63
-
Bramel J, Simchi-Levi D. A location based heuristic for general routing problems. Operations Research. 1995; 43(4): 649-660.
Google Scholar
64
-
Fakhravar H. Combining heuristics and Exact Algorithms: A Review. arXiv preprint arXiv:2202.02799. 2022 Feb 6.
Google Scholar
65
-
Fakhravar H. Quantifying uncertainty in risk assessment using fuzzy theory. arXiv preprint arXiv:2009.09334. 2020 Sep 20.
Google Scholar
66
-
Natarajan G, Ng EH, Katina PF. Systems statistical engineering-hierarchical fuzzy constraint propagation. 2021.
Google Scholar
67