Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

16. GRASP

Authors: Paola Festa, Mauricio G. C. Resende

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

Abstract

GRASP (greedy randomized adaptive search procedure) is a multistart metaheuristic for computing good-quality solutions of combinatorial optimization problems. Each GRASP iteration is usually made up of a construction phase, where a feasible solution is constructed, and a local search phase which starts at the constructed solution and applies iterative improvement until a locally optimal solution is found. Typically, the construction phase of GRASP is a randomized greedy algorithm, but other types of construction procedures have been also proposed. Repeated applications of a construction procedure yields diverse starting solutions for the local search. This chapter gives an overview of GRASP describing its basic components and enhancements to the basic procedure, including reactive GRASP and intensification strategies.
Literature
1.
go back to reference Abdinnour-Helm S, Hadley S (2000) Tabu search based heuristics for multi-floor facility layout. Int J Prod Res 38:365–383 Abdinnour-Helm S, Hadley S (2000) Tabu search based heuristics for multi-floor facility layout. Int J Prod Res 38:365–383
2.
go back to reference Abello J, Pardalos P, Resende M (1999) On maximum clique problems in very large graphs. In: Abello J, Vitter J (eds) External memory algorithms and visualization. DIMACS series on discrete mathematics and theoretical computer science, vol 50. American Mathematical Society, Providence, pp 199–130 Abello J, Pardalos P, Resende M (1999) On maximum clique problems in very large graphs. In: Abello J, Vitter J (eds) External memory algorithms and visualization. DIMACS series on discrete mathematics and theoretical computer science, vol 50. American Mathematical Society, Providence, pp 199–130
3.
go back to reference Ahuja R, Orlin J, Tiwari A (2000) A greedy genetic algorithm for the quadratic assignment problem. Comput Oper Res 27:917–934 Ahuja R, Orlin J, Tiwari A (2000) A greedy genetic algorithm for the quadratic assignment problem. Comput Oper Res 27:917–934
4.
go back to reference Aiex R, Binato S, Resende M (2003) Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput 29:393–430 Aiex R, Binato S, Resende M (2003) Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput 29:393–430
5.
go back to reference Aiex R, Resende M, Pardalos P, Toraldo G (2005) GRASP with path relinking for three-index assignment. INFORMS J Comput 17(2):224–247 Aiex R, Resende M, Pardalos P, Toraldo G (2005) GRASP with path relinking for three-index assignment. INFORMS J Comput 17(2):224–247
6.
go back to reference Alvarez-Valdes R, Parreño F, Tamarit J (2005) A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. J Oper Res Soc 56(4):414–425 Alvarez-Valdes R, Parreño F, Tamarit J (2005) A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. J Oper Res Soc 56(4):414–425
7.
go back to reference Alvarez-Valdes R, Parreño F, Tamarit J (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35(4):1065–1083 Alvarez-Valdes R, Parreño F, Tamarit J (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35(4):1065–1083
8.
go back to reference Amaldi E, Capone A, Malucelli F (2003) Planning UMTS base station location: optimization models with power control and algorithms. IEEE Trans Wirel Commun 2(5):939–952 Amaldi E, Capone A, Malucelli F (2003) Planning UMTS base station location: optimization models with power control and algorithms. IEEE Trans Wirel Commun 2(5):939–952
9.
go back to reference Andrade D, Resende M (2006) A GRASP for PBX telephone migration scheduling. In: Eighth INFORMS telecommunication conference, Dallas Andrade D, Resende M (2006) A GRASP for PBX telephone migration scheduling. In: Eighth INFORMS telecommunication conference, Dallas
10.
go back to reference Andrade D, Resende M (2007) GRASP with path-relinking for network migration scheduling. In: Proceedings of the international network optimization conference (INOC 2007), Spa Andrade D, Resende M (2007) GRASP with path-relinking for network migration scheduling. In: Proceedings of the international network optimization conference (INOC 2007), Spa
11.
go back to reference Andres C, Miralles C, Pastor R (2008) Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur J Oper Res 187(3):1212–1223 Andres C, Miralles C, Pastor R (2008) Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur J Oper Res 187(3):1212–1223
12.
go back to reference Areibi S (1999) GRASP: an effective constructive technique for VLSI circuit partitioning. In: Proceedings of the IEEE Canadian conference on electrical & computer engineering (CCECE’99), Edmonton Areibi S (1999) GRASP: an effective constructive technique for VLSI circuit partitioning. In: Proceedings of the IEEE Canadian conference on electrical & computer engineering (CCECE’99), Edmonton
13.
go back to reference Areibi S, Vannelli A (1997) A GRASP clustering technique for circuit partitioning. In: Gu J, Pardalos P (eds) Satisfiability problems. DIMACS series on discrete mathematics and theoretical computer science, vol 35. American Mathematical Society, Providence, pp 711–724 Areibi S, Vannelli A (1997) A GRASP clustering technique for circuit partitioning. In: Gu J, Pardalos P (eds) Satisfiability problems. DIMACS series on discrete mathematics and theoretical computer science, vol 35. American Mathematical Society, Providence, pp 711–724
14.
go back to reference Argüello M, Feo T, Goldschmidt O (1996) Randomized methods for the number partitioning problem. Comput Oper Res 23(2):103–111 Argüello M, Feo T, Goldschmidt O (1996) Randomized methods for the number partitioning problem. Comput Oper Res 23(2):103–111
15.
go back to reference Argüello M, Bard J, Yu G (1997) A GRASP for aircraft routing in response to groundings and delays. J Comb Optim 1:211–228 Argüello M, Bard J, Yu G (1997) A GRASP for aircraft routing in response to groundings and delays. J Comb Optim 1:211–228
16.
go back to reference Armony M, Klincewicz J, Luss H, Rosenwein M (2000) Design of stacked self-healing rings using a genetic algorithm. J Heuristics 6:85–105 Armony M, Klincewicz J, Luss H, Rosenwein M (2000) Design of stacked self-healing rings using a genetic algorithm. J Heuristics 6:85–105
17.
go back to reference Arroyo J, Vieira P, Vianna D (2008) A GRASP algorithm for the multi-criteria minimum spanning tree problem. Ann Oper Res 159:125–133 Arroyo J, Vieira P, Vianna D (2008) A GRASP algorithm for the multi-criteria minimum spanning tree problem. Ann Oper Res 159:125–133
18.
go back to reference Atkinson J (1998) A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy. J Oper Res Soc 49:700–708 Atkinson J (1998) A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy. J Oper Res Soc 49:700–708
19.
go back to reference Bäck T, Fogel D, Michalewicz Z (1997) Handbook of evolutionary computation. Oxford University Press, New York Bäck T, Fogel D, Michalewicz Z (1997) Handbook of evolutionary computation. Oxford University Press, New York
20.
go back to reference Bard J (1997) An analysis of a rail car unloading area for a consumer products manufacturer. J Oper Res Soc 48:873–883 Bard J (1997) An analysis of a rail car unloading area for a consumer products manufacturer. J Oper Res Soc 48:873–883
21.
go back to reference Bard J, Feo T (1989) Operations sequencing in discrete parts manufacturing. Manag Sci 35:249–255 Bard J, Feo T (1989) Operations sequencing in discrete parts manufacturing. Manag Sci 35:249–255
22.
go back to reference Bard J, Feo T (1991) An algorithm for the manufacturing equipment selection problem. IIE Trans 23:83–92 Bard J, Feo T (1991) An algorithm for the manufacturing equipment selection problem. IIE Trans 23:83–92
23.
go back to reference Bard J, Huang L, Jaillet P, Dror M (1998) A decomposition approach to the inventory routing problem with satellite facilities. Transp Sci 32:189–203 Bard J, Huang L, Jaillet P, Dror M (1998) A decomposition approach to the inventory routing problem with satellite facilities. Transp Sci 32:189–203
24.
go back to reference Binato S, Oliveira G (2002) A reactive GRASP for transmission network expansion planning. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 81–100 Binato S, Oliveira G (2002) A reactive GRASP for transmission network expansion planning. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 81–100
25.
go back to reference Binato S, Oliveira G, Araújo J (2001) A greedy randomized adaptive search procedure for transmission expansion planning. IEEE Trans Power Syst 16:247–253 Binato S, Oliveira G, Araújo J (2001) A greedy randomized adaptive search procedure for transmission expansion planning. IEEE Trans Power Syst 16:247–253
26.
go back to reference Binato S, Hery W, Loewenstern D, Resende M (2002) A greedy randomized adaptive search procedure for job shop scheduling. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 58–79 Binato S, Hery W, Loewenstern D, Resende M (2002) A greedy randomized adaptive search procedure for job shop scheduling. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 58–79
27.
go back to reference Boudia M, Louly M, Prins C (2007) A reactive GRASP and path relinking for a combined production-distribution problem. Comput Oper Res 34:3402–3419 Boudia M, Louly M, Prins C (2007) A reactive GRASP and path relinking for a combined production-distribution problem. Comput Oper Res 34:3402–3419
28.
go back to reference Bresina J (1996) Heuristic-biased stochastic sampling. In: Proceedings of the thirteenth national conference on artificial intelligence (AAAI-96), Portland, pp 271–278 Bresina J (1996) Heuristic-biased stochastic sampling. In: Proceedings of the thirteenth national conference on artificial intelligence (AAAI-96), Portland, pp 271–278
29.
go back to reference Canuto S, Resende M, Ribeiro C (2001) Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38:50–58 Canuto S, Resende M, Ribeiro C (2001) Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38:50–58
30.
go back to reference Carreto C, Baker B (2002) A GRASP interactive approach to the vehicle routing problem with backhauls. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 185–200 Carreto C, Baker B (2002) A GRASP interactive approach to the vehicle routing problem with backhauls. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 185–200
31.
go back to reference Charon I, Hudry O (1993) The noising method: a new method for combinatorial optimization. Oper Res Lett 14:133–137 Charon I, Hudry O (1993) The noising method: a new method for combinatorial optimization. Oper Res Lett 14:133–137
32.
go back to reference Charon I, Hudry O (2002) The noising methods: a survey. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 245–261 Charon I, Hudry O (2002) The noising methods: a survey. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 245–261
33.
go back to reference Commander C, Festa P, Oliveira C, Pardalos P, Resende M, Tsitselis M (2006) A greedy randomized algorithm for the cooperative communication problem on ad hoc networks. In: Eighth INFORMS telecommunications conference, Dallas Commander C, Festa P, Oliveira C, Pardalos P, Resende M, Tsitselis M (2006) A greedy randomized algorithm for the cooperative communication problem on ad hoc networks. In: Eighth INFORMS telecommunications conference, Dallas
34.
go back to reference Contreras I, Díaz J (2008) Scatter search for the single source capacitated facility location problem. Ann Oper Res 157:73–89 Contreras I, Díaz J (2008) Scatter search for the single source capacitated facility location problem. Ann Oper Res 157:73–89
35.
go back to reference Cravo G, Ribeiro G, Lorena LN (2008) A greedy randomized adaptive search procedure for the point-feature cartographic label placement. Comput Geosci 34(4):373–386 Cravo G, Ribeiro G, Lorena LN (2008) A greedy randomized adaptive search procedure for the point-feature cartographic label placement. Comput Geosci 34(4):373–386
36.
go back to reference Delmaire H, Díaz J, Fernández E, Ortega M (1999) Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem. INFOR 37:194–225 Delmaire H, Díaz J, Fernández E, Ortega M (1999) Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem. INFOR 37:194–225
37.
go back to reference Deshpande A, Triantaphyllou E (1998) A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions. Math Comput Model 27:75–99 Deshpande A, Triantaphyllou E (1998) A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions. Math Comput Model 27:75–99
38.
go back to reference Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
39.
go back to reference Faria H, Binato S, Resende M, Falcão D (2005) Power transmission network design by a greedy randomized adaptive path relinking approach. IEEE Trans Power Syst 20(1):43–49 Faria H, Binato S, Resende M, Falcão D (2005) Power transmission network design by a greedy randomized adaptive path relinking approach. IEEE Trans Power Syst 20(1):43–49
40.
go back to reference Feo T, Bard J (1989) Flight scheduling and maintenance base planning. Manag Sci 35:1415–1432 Feo T, Bard J (1989) Flight scheduling and maintenance base planning. Manag Sci 35:1415–1432
41.
go back to reference Feo T, González-Velarde J (1995) The intermodal trailer assignment problem: models, algorithms, and heuristics. Transp Sci 29:330–341 Feo T, González-Velarde J (1995) The intermodal trailer assignment problem: models, algorithms, and heuristics. Transp Sci 29:330–341
42.
go back to reference Feo T, Resende M (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71 Feo T, Resende M (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71
43.
go back to reference Feo T, Resende M (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133 Feo T, Resende M (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133
44.
go back to reference Feo T, Venkatraman K, Bard J (1991) A GRASP for a difficult single machine scheduling problem. Comput Oper Res 18:635–643 Feo T, Venkatraman K, Bard J (1991) A GRASP for a difficult single machine scheduling problem. Comput Oper Res 18:635–643
45.
go back to reference Feo T, Resende M, Smith S (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 42:860–878 Feo T, Resende M, Smith S (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 42:860–878
46.
go back to reference Feo T, Sarathy K, McGahan J (1996) A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties. Comput Oper Res 23:881–895 Feo T, Sarathy K, McGahan J (1996) A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties. Comput Oper Res 23:881–895
47.
go back to reference Ferone D, Festa P, Resende M (2013) Hybrid metaheuristics for the far from most string problem. In: Proceedings of 8th international workshop on hybrid metaheuristics. Lecture notes in computer science, vol 7919. Springer, Berlin/New York, pp 174–188 Ferone D, Festa P, Resende M (2013) Hybrid metaheuristics for the far from most string problem. In: Proceedings of 8th international workshop on hybrid metaheuristics. Lecture notes in computer science, vol 7919. Springer, Berlin/New York, pp 174–188
48.
go back to reference Ferone D, Festa P, Resende M (2016) Hybridizations of GRASDP with path-relinking for the far from most string problem. Int Trans Oper Res 23(3):481–506 Ferone D, Festa P, Resende M (2016) Hybridizations of GRASDP with path-relinking for the far from most string problem. Int Trans Oper Res 23(3):481–506
49.
go back to reference Festa P (2007) On some optimization problems in molecular biology. Math Biosci 207(2):219–234 Festa P (2007) On some optimization problems in molecular biology. Math Biosci 207(2):219–234
50.
go back to reference Festa P, Resende M (2002) GRASP: an annotated bibliography. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 325–367 Festa P, Resende M (2002) GRASP: an annotated bibliography. In: Ribeiro C, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 325–367
51.
go back to reference Festa P, Resende M (2013) Hybridizations of GRASP with path-relinking. In: Talbi EG (ed) Hybrid metaheuristics – studies in computational intelligence, vol 434. Springer, Berlin/New York, pp 135–155 Festa P, Resende M (2013) Hybridizations of GRASP with path-relinking. In: Talbi EG (ed) Hybrid metaheuristics – studies in computational intelligence, vol 434. Springer, Berlin/New York, pp 135–155
52.
go back to reference Festa P, Resende MGC (2009) An annotated bibliography of grasp – part I: algorithms. Int Trans Oper Res 16(1):1–24 Festa P, Resende MGC (2009) An annotated bibliography of grasp – part I: algorithms. Int Trans Oper Res 16(1):1–24
53.
go back to reference Festa P, Resende MGC (2009) An annotated bibliography of grasp – part II: applications. Int Trans Oper Res 16(2):131–172 Festa P, Resende MGC (2009) An annotated bibliography of grasp – part II: applications. Int Trans Oper Res 16(2):131–172
54.
go back to reference Festa P, Pardalos P, Resende M (2001) Algorithm 815: FORTRAN subroutines for computing approximate solution to feedback set problems using GRASP. ACM Trans Math Softw 27:456–464 Festa P, Pardalos P, Resende M (2001) Algorithm 815: FORTRAN subroutines for computing approximate solution to feedback set problems using GRASP. ACM Trans Math Softw 27:456–464
55.
go back to reference Festa P, Pardalos P, Resende M, Ribeiro C (2002) Randomized heuristics for the MAX-CUT problem. Optim Methods Softw 7:1033–1058 Festa P, Pardalos P, Resende M, Ribeiro C (2002) Randomized heuristics for the MAX-CUT problem. Optim Methods Softw 7:1033–1058
56.
go back to reference Festa P, Pardalos P, Pitsoulis L, Resende M (2006) GRASP with path-relinking for the weighted MAXSAT problem. ACM J Exp Algorithmics 11:1–16 Festa P, Pardalos P, Pitsoulis L, Resende M (2006) GRASP with path-relinking for the weighted MAXSAT problem. ACM J Exp Algorithmics 11:1–16
57.
go back to reference Festa P, Gonçalves J, Resende M, Silva R (2010) Automatic tuning of GRASP with path-relinking heuristics with a biased random-key genetic algorithm. In: Festa P (ed) Proceedings of 9th international symposium on experimental algorithms. Lecture notes in computer science, vol 6049. Springer, Berlin/New York, pp 338–349 Festa P, Gonçalves J, Resende M, Silva R (2010) Automatic tuning of GRASP with path-relinking heuristics with a biased random-key genetic algorithm. In: Festa P (ed) Proceedings of 9th international symposium on experimental algorithms. Lecture notes in computer science, vol 6049. Springer, Berlin/New York, pp 338–349
58.
go back to reference Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 11:198–204 Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 11:198–204
59.
go back to reference Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, New York Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, New York
60.
go back to reference Ghosh J (1996) Computational aspects of the maximum diversity problem. Oper Res Lett 19:175–181 Ghosh J (1996) Computational aspects of the maximum diversity problem. Oper Res Lett 19:175–181
61.
go back to reference Glover F (1989) Tabu search – part I. ORSA J Comput 1:190–206 Glover F (1989) Tabu search – part I. ORSA J Comput 1:190–206
62.
go back to reference Glover F (1990) Tabu search – part II. ORSA J on Comput 2:4–32 Glover F (1990) Tabu search – part II. ORSA J on Comput 2:4–32
63.
go back to reference Glover F (1996) Tabu search and adaptive memory programing – advances, applications and challenges. In: Barr R, Helgason R, Kennington J (eds) Interfaces in computer science and operations research. Kluwer Academic Publishers, Boston, pp 1–75 Glover F (1996) Tabu search and adaptive memory programing – advances, applications and challenges. In: Barr R, Helgason R, Kennington J (eds) Interfaces in computer science and operations research. Kluwer Academic Publishers, Boston, pp 1–75
64.
go back to reference Glover F (2000) Multi-start and strategic oscillation methods – principles to exploit adaptive memory. In: Laguna M, Gonzáles-Velarde J (eds) Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research. Kluwer Academic Publishers, Boston, pp 1–24 Glover F (2000) Multi-start and strategic oscillation methods – principles to exploit adaptive memory. In: Laguna M, Gonzáles-Velarde J (eds) Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research. Kluwer Academic Publishers, Boston, pp 1–24
65.
go back to reference Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston
66.
go back to reference Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684 Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
67.
go back to reference Goëffon A, Richer JM, Hao JK (2008) Progressive tree neighborhood applied to the maximum parsimony problem. IEEE/ACM Trans Comput Biol Bioinform 5(1):136–145 Goëffon A, Richer JM, Hao JK (2008) Progressive tree neighborhood applied to the maximum parsimony problem. IEEE/ACM Trans Comput Biol Bioinform 5(1):136–145
68.
go back to reference Goemans M, Williamson D (1996) The primal dual method for approximation algorithms and its application to network design problems. In: Hochbaum D (ed) Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston, pp 144–191 Goemans M, Williamson D (1996) The primal dual method for approximation algorithms and its application to network design problems. In: Hochbaum D (ed) Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston, pp 144–191
69.
go back to reference Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading
70.
go back to reference Gonçalves J, Resende M (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17(5):487–525 Gonçalves J, Resende M (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17(5):487–525
71.
go back to reference Hammer P, Rader D Jr (2001) Maximally disjoint solutions of the set covering problem. J Heuristics 7:131–144 Hammer P, Rader D Jr (2001) Maximally disjoint solutions of the set covering problem. J Heuristics 7:131–144
72.
go back to reference Hansen P, Mladenović N (1998) An introduction to variable neighborhood search. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics, advances and trends in local search paradigms for optimization. Kluwer Academic Publishers, Boston, pp 433–458 Hansen P, Mladenović N (1998) An introduction to variable neighborhood search. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics, advances and trends in local search paradigms for optimization. Kluwer Academic Publishers, Boston, pp 433–458
73.
go back to reference Hansen P, Mladenović N (2002) Developments of variable neighborhood search. In: Ribeiro C, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Boston, pp 415–439 Hansen P, Mladenović N (2002) Developments of variable neighborhood search. In: Ribeiro C, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Boston, pp 415–439
74.
go back to reference Hart J, Shogan A (1987) Semi-greedy heuristics: an empirical study. Oper Res Lett 6:107–114 Hart J, Shogan A (1987) Semi-greedy heuristics: an empirical study. Oper Res Lett 6:107–114
75.
go back to reference Hirsch M, Meneses C, Pardalos P, Ragle M, Resende M (2007) A continuous GRASP to determine the relationship between drugs and adverse reactions. In: Seref O, Kundakcioglu O, Pardalos P (eds) Data mining, systems analysis, and optimization in biomedicine. AIP conference proceedings, vol 953. Springer, Melville, pp 106–121 Hirsch M, Meneses C, Pardalos P, Ragle M, Resende M (2007) A continuous GRASP to determine the relationship between drugs and adverse reactions. In: Seref O, Kundakcioglu O, Pardalos P (eds) Data mining, systems analysis, and optimization in biomedicine. AIP conference proceedings, vol 953. Springer, Melville, pp 106–121
76.
go back to reference Hutter F, Hoos H, Leyton-Brown K, Stützle T (2009) ParamILS: an automatic algorithm configuration framework. J Artif Intell Res 36:267–306 Hutter F, Hoos H, Leyton-Brown K, Stützle T (2009) ParamILS: an automatic algorithm configuration framework. J Artif Intell Res 36:267–306
77.
go back to reference Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning problems. Bell Syst Tech J 49(2):291–307 Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning problems. Bell Syst Tech J 49(2):291–307
78.
go back to reference Kirkpatrick S (1984) Optimization by simulated annealing: quantitative studies. J Stat Phys 34:975–986 Kirkpatrick S (1984) Optimization by simulated annealing: quantitative studies. J Stat Phys 34:975–986
79.
go back to reference Klincewicz J (1992) Avoiding local optima in the p-hub location problem using tabu search and GRASP. Ann Oper Res 40:283–302 Klincewicz J (1992) Avoiding local optima in the p-hub location problem using tabu search and GRASP. Ann Oper Res 40:283–302
80.
go back to reference Klincewicz J, Rajan A (1994) Using GRASP to solve the component grouping problem. Nav Res Logist 41:893–912 Klincewicz J, Rajan A (1994) Using GRASP to solve the component grouping problem. Nav Res Logist 41:893–912
81.
go back to reference Kontoravdis G, Bard J (1995) A GRASP for the vehicle routing problem with time windows. ORSA J Comput 7:10–23 Kontoravdis G, Bard J (1995) A GRASP for the vehicle routing problem with time windows. ORSA J Comput 7:10–23
82.
go back to reference Laguna M, González-Velarde J (1991) A search heuristic for just-in-time scheduling in parallel machines. J Intell Manuf 2:253–260 Laguna M, González-Velarde J (1991) A search heuristic for just-in-time scheduling in parallel machines. J Intell Manuf 2:253–260
83.
go back to reference Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52 Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52
84.
go back to reference Laguna M, Martí R (2001) A GRASP for coloring sparse graphs. Comput Optim Appl 19:165–178 Laguna M, Martí R (2001) A GRASP for coloring sparse graphs. Comput Optim Appl 19:165–178
85.
go back to reference Laguna M, Feo T, Elrod H (1994) A greedy randomized adaptive search procedure for the two-partition problem. Oper Res 42:677–687 Laguna M, Feo T, Elrod H (1994) A greedy randomized adaptive search procedure for the two-partition problem. Oper Res 42:677–687
86.
go back to reference Li Y, Pardalos P, Resende M (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos P, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS series on discrete mathematics and theoretical computer science, vol 16. American Mathematical Society, Providence, pp 237–261 Li Y, Pardalos P, Resende M (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos P, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS series on discrete mathematics and theoretical computer science, vol 16. American Mathematical Society, Providence, pp 237–261
87.
go back to reference Liu X, Pardalos P, Rajasekaran S, Resende M (2000) A GRASP for frequency assignment in mobile radio networks. In: Rajasekaran S, Pardalos P, Hsu F (eds) Mobile networks and computing. DIMACS series on discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence, pp 195–201 Liu X, Pardalos P, Rajasekaran S, Resende M (2000) A GRASP for frequency assignment in mobile radio networks. In: Rajasekaran S, Pardalos P, Hsu F (eds) Mobile networks and computing. DIMACS series on discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence, pp 195–201
88.
go back to reference Lourenço HR, Paixão J, Portugal R (2001) Multiobjective metaheuristics for the bus-driver scheduling problem. Transp Sci 35:331–343 Lourenço HR, Paixão J, Portugal R (2001) Multiobjective metaheuristics for the bus-driver scheduling problem. Transp Sci 35:331–343
89.
go back to reference Martí R, Laguna M (2003) Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discret Appl Math 127(3):665–678 Martí R, Laguna M (2003) Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discret Appl Math 127(3):665–678
90.
go back to reference Martins S, Ribeiro C, Souza M (1998) A parallel GRASP for the Steiner problem in graphs. In: Ferreira A, Rolim J (eds) Proceedings of IRREGULAR’98 – 5th international symposium on solving irregularly structured problems in parallel. Lecture notes in computer science, vol 1457. Springer, Berlin/Heidelberg, pp 285–297 Martins S, Ribeiro C, Souza M (1998) A parallel GRASP for the Steiner problem in graphs. In: Ferreira A, Rolim J (eds) Proceedings of IRREGULAR’98 – 5th international symposium on solving irregularly structured problems in parallel. Lecture notes in computer science, vol 1457. Springer, Berlin/Heidelberg, pp 285–297
91.
go back to reference Martins S, Pardalos P, Resende M, Ribeiro C (1999) Greedy randomized adaptive search procedures for the Steiner problem in graphs. In: Pardalos P, Rajasekaran S, Rolim J (eds) Randomization methods in algorithmic design. DIMACS series on discrete mathematics and theoretical computer science, vol 43. American Mathematical Society, Providence, pp 133–145 Martins S, Pardalos P, Resende M, Ribeiro C (1999) Greedy randomized adaptive search procedures for the Steiner problem in graphs. In: Pardalos P, Rajasekaran S, Rolim J (eds) Randomization methods in algorithmic design. DIMACS series on discrete mathematics and theoretical computer science, vol 43. American Mathematical Society, Providence, pp 133–145
92.
go back to reference Martins S, Resende M, Ribeiro C, Pardalos P (2000) A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. J Glob Optim 17:267–283 Martins S, Resende M, Ribeiro C, Pardalos P (2000) A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. J Glob Optim 17:267–283
93.
go back to reference Mavridou T, Pardalos P, Pitsoulis L, Resende M (1998) A GRASP for the biquadratic assignment problem. Eur J Oper Res 105:613–621 Mavridou T, Pardalos P, Pitsoulis L, Resende M (1998) A GRASP for the biquadratic assignment problem. Eur J Oper Res 105:613–621
94.
go back to reference Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24: 1097–1100 Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24: 1097–1100
95.
go back to reference Mockus J, Eddy E, Mockus A, Mockus L, Reklaitis G (1997) Bayesian discrete and global optimization. Kluwer Academic Publishers, Dordrecht/Boston Mockus J, Eddy E, Mockus A, Mockus L, Reklaitis G (1997) Bayesian discrete and global optimization. Kluwer Academic Publishers, Dordrecht/Boston
96.
go back to reference Monkman S, Morrice D, Bard J (2008) A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs. Eur J Oper Res 187(3): 1100–1114 Monkman S, Morrice D, Bard J (2008) A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs. Eur J Oper Res 187(3): 1100–1114
97.
go back to reference Morán-Mirabal L, González-Velarde J, Resende M (2013) Automatic tuning of GRASP with evolutionary path-relinking. In: Proceedings of 8th international workshop on hybrid metaheuristics, Ischia. Lecture notes in computer science, vol 7919, pp 62–77 Morán-Mirabal L, González-Velarde J, Resende M (2013) Automatic tuning of GRASP with evolutionary path-relinking. In: Proceedings of 8th international workshop on hybrid metaheuristics, Ischia. Lecture notes in computer science, vol 7919, pp 62–77
98.
go back to reference nez MLI, Dubois-Lacoste J, Stützle T, Birattari M (2011) The IRACE package, iterated race for automatic algorithm configuration. Technical report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles nez MLI, Dubois-Lacoste J, Stützle T, Birattari M (2011) The IRACE package, iterated race for automatic algorithm configuration. Technical report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles
99.
go back to reference Osman I, Al-Ayoubi B, Barake M (2003) A greedy random adaptive search procedure for the weighted maximal planar graph problem. Comput Ind Eng 45(4):635–651 Osman I, Al-Ayoubi B, Barake M (2003) A greedy random adaptive search procedure for the weighted maximal planar graph problem. Comput Ind Eng 45(4):635–651
100.
go back to reference Pardalos P, Pitsoulis L, Resende M (1996) A parallel GRASP for MAX-SAT problems. Lect Notes Comput Sci 1184:575–585 Pardalos P, Pitsoulis L, Resende M (1996) A parallel GRASP for MAX-SAT problems. Lect Notes Comput Sci 1184:575–585
101.
go back to reference Pardalos P, Pitsoulis L, Resende M (1997) Algorithm 769: Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP. ACM Trans Math Softw 23:196–208 Pardalos P, Pitsoulis L, Resende M (1997) Algorithm 769: Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP. ACM Trans Math Softw 23:196–208
102.
go back to reference Pardalos P, Ramakrishnan K, Resende M, Li Y (1997) Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem. SIAM J Optim 7:280–294 Pardalos P, Ramakrishnan K, Resende M, Li Y (1997) Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem. SIAM J Optim 7:280–294
103.
go back to reference Pinãna E, Plana I, Campos V, R Martì (2004) GRASP and path relinking for the matrix bandwidth minimization. Eur J Oper Res 153(1):200–210 Pinãna E, Plana I, Campos V, R Martì (2004) GRASP and path relinking for the matrix bandwidth minimization. Eur J Oper Res 153(1):200–210
104.
go back to reference Prais M, Ribeiro C (1999) Parameter variation in GRASP implementations. In: Extended abstracts of the third metaheuristics international conference, Porto, pp 375–380 Prais M, Ribeiro C (1999) Parameter variation in GRASP implementations. In: Extended abstracts of the third metaheuristics international conference, Porto, pp 375–380
105.
go back to reference Prais M, Ribeiro C (2000) Parameter variation in GRASP procedures. Investigación Operativa 9:1–20 Prais M, Ribeiro C (2000) Parameter variation in GRASP procedures. Investigación Operativa 9:1–20
106.
go back to reference Prais M, Ribeiro C (2000) Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J Comput 12:164–176 Prais M, Ribeiro C (2000) Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J Comput 12:164–176
107.
go back to reference Pu G, Chong Z, Qiu Z, Lin Z, He J (2006) A hybrid heuristic algorithm for HW-SW partitioning within timed automata. In: Proceedings of knowledge-based intelligent information and engineering systems. Lecture notes in artificial intelligence, vol 4251. Springer, Berlin/Heidelberg, pp 459–466 Pu G, Chong Z, Qiu Z, Lin Z, He J (2006) A hybrid heuristic algorithm for HW-SW partitioning within timed automata. In: Proceedings of knowledge-based intelligent information and engineering systems. Lecture notes in artificial intelligence, vol 4251. Springer, Berlin/Heidelberg, pp 459–466
108.
go back to reference Resende M, Feo T (1996) A GRASP for satisfiability. In: Johnson D, Trick M (eds) Cliques, coloring, and satisfiability: the second DIMACS implementation challenge. DIMACS series on discrete mathematics and theoretical computer science, vol 26. American Mathematical Society, Providence, pp 499–520 Resende M, Feo T (1996) A GRASP for satisfiability. In: Johnson D, Trick M (eds) Cliques, coloring, and satisfiability: the second DIMACS implementation challenge. DIMACS series on discrete mathematics and theoretical computer science, vol 26. American Mathematical Society, Providence, pp 499–520
109.
go back to reference Resende M, Ribeiro C (1997) A GRASP for graph planarization. Networks 29:173–189 Resende M, Ribeiro C (1997) A GRASP for graph planarization. Networks 29:173–189
110.
go back to reference Resende M, Ribeiro C (2003) Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic Publishers, Boston, pp 219–249 Resende M, Ribeiro C (2003) Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic Publishers, Boston, pp 219–249
111.
go back to reference Resende M, Ribeiro C (2005) GRASP with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Springer, New York, pp 29–63 Resende M, Ribeiro C (2005) GRASP with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Springer, New York, pp 29–63
112.
go back to reference Resende M, Pardalos P, Li Y (1996) Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP. ACM Trans Math Softw 22:104–118 Resende M, Pardalos P, Li Y (1996) Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP. ACM Trans Math Softw 22:104–118
113.
go back to reference Resende M, Pitsoulis L, Pardalos P (1997) Approximate solution of weighted MAX-SAT problems using GRASP. In: Gu J, Pardalos P (eds) Satisfiability problems. DIMACS series on discrete mathematics and theoretical computer science, vol 35. American Mathematical Society, Providence, pp 393–405 Resende M, Pitsoulis L, Pardalos P (1997) Approximate solution of weighted MAX-SAT problems using GRASP. In: Gu J, Pardalos P (eds) Satisfiability problems. DIMACS series on discrete mathematics and theoretical computer science, vol 35. American Mathematical Society, Providence, pp 393–405
114.
go back to reference Resende M, Pitsoulis L, Pardalos P (2000) Fortran subroutines for computing approximate solutions of MAX-SAT problems using GRASP. Discret Appl Math 100:95–113 Resende M, Pitsoulis L, Pardalos P (2000) Fortran subroutines for computing approximate solutions of MAX-SAT problems using GRASP. Discret Appl Math 100:95–113
115.
go back to reference Ribeiro C, Resende M (1999) Fortran subroutines for approximate solution of graph planarization problems using GRASP. ACM Trans Math Softw 25:341–352 Ribeiro C, Resende M (1999) Fortran subroutines for approximate solution of graph planarization problems using GRASP. ACM Trans Math Softw 25:341–352
116.
go back to reference Ribeiro C, Souza M (2002) Variable neighborhood search for the degree constrained minimum spanning tree problem. Discret Appl Math 118:43–54 Ribeiro C, Souza M (2002) Variable neighborhood search for the degree constrained minimum spanning tree problem. Discret Appl Math 118:43–54
117.
go back to reference Ribeiro C, Urrutia S (2007) Heuristics for the mirrored traveling tournament problem. Eur J Oper Res 179:775–787 Ribeiro C, Urrutia S (2007) Heuristics for the mirrored traveling tournament problem. Eur J Oper Res 179:775–787
118.
go back to reference Ribeiro C, Uchoa E, Werneck R (2002) A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J Comput 14:228–246 Ribeiro C, Uchoa E, Werneck R (2002) A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J Comput 14:228–246
119.
go back to reference Ríos-Mercado R, Bard J (1998) Heuristics for the flow line problem with setup costs. Eur J Oper Res 110(1):76–98 Ríos-Mercado R, Bard J (1998) Heuristics for the flow line problem with setup costs. Eur J Oper Res 110(1):76–98
120.
go back to reference Ríos-Mercado R, Bard J (1999) An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup costs. J Heuristics 5:57–74 Ríos-Mercado R, Bard J (1999) An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup costs. J Heuristics 5:57–74
121.
go back to reference Rivera L (1998) Evaluation of parallel implementations of heuristics for the course scheduling problem. Master’s thesis, Instituto Tecnologico y de Estudios Superiores de Monterrey, Monterrey Rivera L (1998) Evaluation of parallel implementations of heuristics for the course scheduling problem. Master’s thesis, Instituto Tecnologico y de Estudios Superiores de Monterrey, Monterrey
122.
go back to reference Robertson A (2001) A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem. Comput Optim Appl 19: 145–164 MathSciNetCrossRef Robertson A (2001) A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem. Comput Optim Appl 19: 145–164 MathSciNetCrossRef
123.
go back to reference Sosnowska D (2000) Optimization of a simplified fleet assignment problem with metaheuristics: simulated annealing and GRASP. In: Pardalos P (ed) Approximation and complexity in numerical optimization. Kluwer Academic Publishers, Boston MATH Sosnowska D (2000) Optimization of a simplified fleet assignment problem with metaheuristics: simulated annealing and GRASP. In: Pardalos P (ed) Approximation and complexity in numerical optimization. Kluwer Academic Publishers, Boston MATH
124.
go back to reference Srinivasan A, Ramakrishnan K, Kumaram K, Aravamudam M, Naqvi S (2000) Optimal design of signaling networks for Internet telephony. In: IEEE INFOCOM 2000, Tel-Aviv, vol 2, pp 707–716 Srinivasan A, Ramakrishnan K, Kumaram K, Aravamudam M, Naqvi S (2000) Optimal design of signaling networks for Internet telephony. In: IEEE INFOCOM 2000, Tel-Aviv, vol 2, pp 707–716
125.
go back to reference Takahashi H, Matsuyama A (1980) An approximate solution for the Steiner problem in graphs. Math Jpn 24:573–577 MathSciNetMATH Takahashi H, Matsuyama A (1980) An approximate solution for the Steiner problem in graphs. Math Jpn 24:573–577 MathSciNetMATH
126.
go back to reference Urban T (1998) Solution procedures for the dynamic facility layout problem. Ann Oper Res 76:323–342 CrossRef Urban T (1998) Solution procedures for the dynamic facility layout problem. Ann Oper Res 76:323–342 CrossRef
Metadata
Title
GRASP
Authors
Paola Festa
Mauricio G. C. Resende
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_23

Premium Partner